DevPath
Tracks

Bitwise Operations

Work directly with the bits of integers: AND, OR, XOR, NOT, shifts, masks, flags, and classic tricks like counting bits and finding the unpaired number.

intermediate35 min#bits#bitwise#xor#masks#binary

Prerequisites: How Computers Run Programs

Why it matters

Under every integer is a row of bits, and sometimes the cheapest or cleverest solution works on those bits directly. Permission flags, network masks, hash functions, compression, graphics, and subset enumeration all use them. In interviews, bit tricks turn problems that seem to need a hash table into O(1)-space one-liners. The operations themselves are few; the skill is recognizing the patterns.

Intuition

Write a number in binary and think of each bit as a light switch: on (1) or off (0). An integer is a panel of switches. Bitwise operators act on all switches at once, each position independently.

  • AND keeps a switch on only if it is on in both panels. Use it to test or clear bits (a mask picks which switches you look at).
  • OR turns a switch on if it is on in either. Use it to set bits.
  • XOR turns a switch on if the two panels differ. XOR with the same value twice returns the original, and any value XOR itself is zero.
  • NOT flips every switch.
  • Shifts slide the whole panel left or right. A left shift by k multiplies by 2^k; a right shift by k divides by 2^k, rounding down.
    1100  (12)         1100          1100
 &  1010  (10)      |  1010       ^  1010
 ------             ------         ------
    1000  (8)          1110 (14)      0110 (6)

The same example as a grid of bits, column by column.

8421
12
1
1
0
0
10
1
0
1
0
12 & 10 = 8
1
0
0
0
12 | 10 = 14
1
1
1
0
12 ^ 10 = 6
0
1
1
0
Each column is computed on its own. AND is 1 only where both rows have a 1 (just the 8s column). OR is 1 where either does. XOR is 1 only where the rows differ.

How it works

The operators are spelled the same in both languages:

  • AND: a & b, 1 where both are 1
  • OR: a | b, 1 where either is 1
  • XOR: a ^ b, 1 where they differ
  • NOT: ~a, flip all bits
  • Left shift: a << k, multiply by 2^k
  • Right shift: a >> k, divide by 2^k, rounding down
ABA & BA | BA ^ B
0
0
0
0
0
0
1
0
1
1
1
0
0
1
1
1
1
1
1
0
Truth table for one bit. AND needs both inputs on, OR needs at least one, XOR needs exactly one. A column of results like this is applied to every bit position at once.

Masks and flags

Give each option its own bit: READ = 1 << 0, WRITE = 1 << 1, EXEC = 1 << 2. Then a set of options is one integer.

  • Set a flag: perms |= EXEC
  • Clear a flag: perms &= ~WRITE
  • Test a flag: perms & READ is nonzero when set
  • Toggle a flag: perms ^= READ

Handy identities

  • Is bit i set? (n >> i) & 1
  • Clear the lowest set bit: n & (n - 1). Subtracting 1 flips the lowest 1 and the zeros below it, so AND removes exactly that bit. Repeating it until zero counts the set bits (Kernighan's method), one loop per set bit.
  • Power of two check: a power of two has exactly one set bit, so n > 0 and n & (n - 1) == 0.
  • Isolate the lowest set bit: n & -n.
  • Swap or cancel: x ^ x = 0 and x ^ 0 = x, and XOR is commutative and associative. XOR-ing a list where every value appears twice except one leaves that one value.

Signed numbers and language differences

Integers use two's complement: for 8 bits, -1 is 11111111, and the top bit means negative. A right shift of a negative number keeps the sign (an arithmetic shift), so -8 >> 1 is -4.

1286432168421
5
0
0
0
0
0
1
0
1
5 << 3 = 40
0
0
1
0
1
0
0
0
100
0
1
1
0
0
1
0
0
100 >> 2 = 25
0
0
0
1
1
0
0
1
-8
1
1
1
1
1
0
0
0
-8 >> 1 = -4
1
1
1
1
1
1
0
0
Eight-bit rows. A left shift slides the 1s toward larger place values (5 becomes 40). A right shift slides them down, and for a negative number the new top bit is a copy of the sign bit (amber), so -8 becomes -4 and stays negative.

The languages differ in width. Python integers have unlimited size, so ~5 is -6 (that is -5 - 1) and bits never overflow. JavaScript converts operands to 32-bit signed integers for bitwise operators, so values above about 2.1 billion wrap, and >>> gives an unsigned right shift. For larger values in JavaScript use BigInt.

OperationTimeNotes
AND / OR / XOR / NOT / shiftO(1)One CPU instruction for word-size values
Test, set, clear one bitO(1)Mask and combine
Count set bits (Kernighan)O(k)k is the number of 1 bits
Enumerate all subsets of n itemsO(2^n)Count from 0 to 2^n - 1; each mask is a subset

Code: popcount, power of two, XOR, and flags

def popcount(n):
    count = 0
    while n:
        n &= n - 1          # clears the lowest set bit
        count += 1
    return count
 
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0
 
def single_number(nums):
    result = 0
    for x in nums:
        result ^= x         # pairs cancel: x ^ x == 0
    return result
 
def yes(flag):
    return "true" if flag else "false"
 
READ, WRITE, EXEC = 1 << 0, 1 << 1, 1 << 2
perms = READ | WRITE
perms &= ~WRITE             # clear a flag
perms |= EXEC               # set a flag
 
print(popcount(0b101101), yes(is_power_of_two(64)), yes(is_power_of_two(96)))
print(single_number([4, 7, 4, 9, 7]))
print(yes(perms & READ), yes(perms & WRITE), yes(perms & EXEC), bin(perms))
print(bin(0b1100 ^ 0b1010), 5 << 3, 100 >> 2, -8 >> 1)

Both versions print:

4 true false
9
true false true 0b101
0b110 40 25 -4

0b101101 has four 1 bits. 64 is 1000000 (one bit); 96 is 1100000 (two). The XOR of 4, 7, 4, 9, 7 cancels both pairs and leaves 9. The permission set ends as read plus exec, 0b101. Last line: 12 ^ 10 = 6, 5 * 8 = 40, 100 / 4 = 25, and -8 / 2 = -4.

Here is the popcount loop on 0b101101 (45), one iteration per step.

1
32
0
16
1
8
1
4
0
2
1
1
Start: n = 45 = 101101, count = 0. The lowest set bit is the 1s place.
step 1 / 5

Each n & (n - 1) deletes exactly the lowest 1 bit, so the loop runs once per set bit: 4 times for 45. The amber cell is the bit that was just cleared.

Common pitfalls

  • Operator precedence: in many languages comparison binds tighter than bitwise AND. n & 1 == 0 parses as n & (1 == 0) in JavaScript. Always parenthesize: (n & 1) === 0.
  • Confusing & with &&: logical operators short-circuit on truthiness; bitwise operators work on every bit. 2 & 1 is 0 (false), while 2 && 1 is 1.
  • JavaScript's 32-bit limit: 2 ** 32 | 0 is 0. Do not use bitwise operators on big values or on floating-point numbers (they truncate).
  • Negative numbers: ~n equals -n - 1. Shifts of negatives are arithmetic, and >>> in JavaScript is the only unsigned shift.
  • Shifting by too much: in JavaScript, shift counts are taken modulo 32, so 1 << 32 is 1. In C it is undefined behavior.
  • Clever but unreadable: use bit tricks when they clearly win, and add a comment naming the identity.

Practice

Count set bits easy

Hint

n & (n - 1) removes the lowest 1. How many times can you do that?

Show solution

Loop while n: n &= n - 1; count += 1. The loop runs once per set bit, so O(k) where k is the number of 1s, and uses O(1) space. Check popcount(0) == 0 and popcount(255) == 8.

Single number easy

Hint

What does x ^ x equal, and does the order of XOR matter?

Show solution

XOR every element together. Pairs cancel because x ^ x = 0, order does not matter, and 0 ^ y = y, so the unpaired value remains. O(n) time, O(1) space, versus a hash set with O(n) space. The trick requires that every other value appears exactly twice.

Missing number medium

Hint

XOR the indexes 0..n together with all the values.

Show solution

For an array of n distinct numbers from 0..n with one missing, start x = n, then for each index i do x ^= i ^ nums[i]. Every present value cancels with its index, leaving the missing one. O(n) time, O(1) space, and unlike the sum formula it cannot overflow in fixed-width languages.

Two unpaired numbers hard

Hint

XOR of everything equals a ^ b. Use any set bit of that value to split the numbers into two groups.

Show solution

Let s be the XOR of all numbers, which equals a ^ b and is nonzero since a != b. Take low = s & -s, a bit where a and b differ. Partition the numbers by whether they have that bit. Each group contains one of the singles plus complete pairs, so XOR-ing each group isolates a and b. O(n) time, O(1) space.

Interview questions

  1. How do you check whether an integer is a power of two? It has exactly one set bit: n > 0 and n & (n - 1) == 0.
  2. How do you swap two numbers without a temporary? a ^= b; b ^= a; a ^= b. It works but is mostly a curiosity; tuple swap is clearer.
  3. What is the difference between >> and >>>? Arithmetic shift keeps the sign bit; logical shift fills with zeros (JavaScript only).
  4. How do you represent a set of up to 32 options in one integer? One bit per option, with OR to add, AND with NOT to remove, and AND to test.

Interviewers look for: knowing n & (n - 1) and XOR cancellation by heart, parenthesizing expressions, and awareness of integer width and signs.

Quick check

What does n & (n - 1) do to a positive integer n?

Finished this lesson?

Further resources

Related lessons