Bit Manipulation
Bit Manipulation Basics
Bit tricks are rarely the right tool in application code and are asked about constantly in interviews. Learn the handful that come up; resist using them where a boolean would read better.
The operators
What each one does
javascript
// AND — 1 only where both are 1
console.log(0b1100 & 0b1010) // 0b1000 = 8
// OR — 1 where either is 1
console.log(0b1100 | 0b1010) // 0b1110 = 14
// XOR — 1 where they differ
console.log(0b1100 ^ 0b1010) // 0b0110 = 6
// NOT — flips every bit (and the sign)
console.log(~5) // -6
// Shifts — multiply and divide by powers of two
console.log(5 << 1) // 10
console.log(5 >> 1) // 2XOR, the one worth knowing
XOR cancels: a ^ a === 0 and a ^ 0 === a. That single property solves a family of problems.
Find the unpaired number
javascript
// Every number appears twice except one. O(n) time, O(1) space.
function singleNumber(nums) {
let result = 0
for (const n of nums) result ^= n
return result
}
console.log(singleNumber([4, 1, 2, 1, 2])) // 4
// Swap without a temporary — a party trick, not production code.
let a = 3, b = 7
a ^= b; b ^= a; a ^= b
console.log(a, b) // 7 3The pairs cancel to zero regardless of order, leaving only the unmatched value. A Set would also work and cost O(n) memory.
Checking and setting bits
The four standard moves
javascript
const isSet = (n, i) => (n & (1 << i)) !== 0
const setBit = (n, i) => n | (1 << i)
const clearBit = (n, i) => n & ~(1 << i)
const toggle = (n, i) => n ^ (1 << i)
console.log(isSet(0b1010, 1)) // true
console.log(setBit(0b1010, 0)) // 0b1011 = 11Tricks that come up
Worth recognising
javascript
// Even or odd — faster than % 2 and clearer once you know it.
const isEven = (n) => (n & 1) === 0
// Power of two? Exactly one bit set.
const isPowerOfTwo = (n) => n > 0 && (n & (n - 1)) === 0
// Count the set bits.
function countBits(n) {
let count = 0
while (n) {
n &= n - 1 // clears the lowest set bit
count++
}
return count
}
console.log(isPowerOfTwo(16)) // true
console.log(countBits(0b1011)) // 3n & (n - 1) clearing the lowest set bit is the one to remember - it powers both of the last two.
The 32-bit trap
JavaScript numbers are 64-bit floats, but bitwise operators convert to 32-bit signed integers first. Above about 2.1 billion the result is wrong, not merely imprecise.
Where it breaks
javascript
console.log(2 ** 31) // 2147483648 — fine as a number
console.log((2 ** 31) | 0) // -2147483648 — wraps to negative
console.log(1 << 31) // -2147483648
console.log(1 << 32) // 1 — the shift wrapped around
// Use BigInt when you genuinely need more than 32 bits.
console.log(1n << 32n) // 4294967296nThis is why >>> 0 appears in library code - it forces an unsigned 32-bit reading. If your values exceed 32 bits, bitwise operators are the wrong tool.
The operations worth memorising
n & 1- is n odd.n >> 1- halve, discarding the remainder.n & (n - 1)- clear the lowest set bit.n & -n- isolate the lowest set bit.n ^ n === 0- a value XORed with itself cancels.1 << k</code> - a mask with only bit k set.
Where each one earns its place
javascript
// Count set bits: loops once per set bit, not once per bit.
function popCount(n) {
let count = 0
while (n) {
n &= n - 1
count++
}
return count
}
// Every value appears twice except one. XOR cancels the pairs.
function singleNumber(items) {
return items.reduce((a, b) => a ^ b, 0)
}
// Power of two: exactly one bit set.
function isPowerOfTwo(n) {
return n > 0 && (n & (n - 1)) === 0
}
console.log(popCount(13)) // 3
console.log(singleNumber([4, 1, 2, 1, 2])) // 4
console.log(isPowerOfTwo(16)) // trueThe JavaScript caveat
Bitwise operators coerce to 32-bit signed integers. Anything above 2³¹ − 1 wraps around and goes negative, so 1 << 31 is negative and 1 << 32 is 1, not four billion. Use BigInt or plain arithmetic when values can exceed that range.
Also note >>>, the unsigned right shift - it is the one operator that treats the value as unsigned, which is why it appears in hash functions and in the safe midpoint (low + high) >>> 1.