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
kmultiplies by2^k; a right shift bykdivides by2^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.
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 by2^k - Right shift:
a >> k, divide by2^k, rounding down
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 & READis nonzero when set - Toggle a flag:
perms ^= READ
Handy identities
- Is bit
iset?(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 = 0andx ^ 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.
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.
| Operation | Time | Notes |
|---|---|---|
| AND / OR / XOR / NOT / shift | O(1) | One CPU instruction for word-size values |
| Test, set, clear one bit | O(1) | Mask and combine |
| Count set bits (Kernighan) | O(k) | k is the number of 1 bits |
| Enumerate all subsets of n items | O(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)function popcount(n) {
let count = 0;
while (n) {
n &= n - 1; // clears the lowest set bit
count++;
}
return count;
}
function isPowerOfTwo(n) {
return n > 0 && (n & (n - 1)) === 0;
}
function singleNumber(nums) {
let result = 0;
for (const x of nums) result ^= x; // pairs cancel: x ^ x === 0
return result;
}
const yes = (flag) => (flag ? "true" : "false");
const READ = 1 << 0, WRITE = 1 << 1, EXEC = 1 << 2;
let perms = READ | WRITE;
perms &= ~WRITE; // clear a flag
perms |= EXEC; // set a flag
console.log(popcount(0b101101), yes(isPowerOfTwo(64)), yes(isPowerOfTwo(96)));
console.log(singleNumber([4, 7, 4, 9, 7]));
console.log(yes(perms & READ), yes(perms & WRITE), yes(perms & EXEC), "0b" + perms.toString(2));
console.log("0b" + (0b1100 ^ 0b1010).toString(2), 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.
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 == 0parses asn & (1 == 0)in JavaScript. Always parenthesize:(n & 1) === 0. - Confusing
&with&&: logical operators short-circuit on truthiness; bitwise operators work on every bit.2 & 1is 0 (false), while2 && 1is 1. - JavaScript's 32-bit limit:
2 ** 32 | 0is 0. Do not use bitwise operators on big values or on floating-point numbers (they truncate). - Negative numbers:
~nequals-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 << 32is 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
- 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. - 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. - What is the difference between
>>and>>>? Arithmetic shift keeps the sign bit; logical shift fills with zeros (JavaScript only). - 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
- Bitwise operation (Wikipedia) (article)
- MDN: Bitwise AND (docs)
- Python docs: bitwise operations on integers (docs)