Bit manipulation

In short

Bit manipulation is the use of the bitwise operators (AND, OR, XOR, NOT, shifts) to read, set and transform the individual binary digits of an integer, treating the integer as a fixed-width array of flags rather than as a quantity. It matters because a single machine instruction does work that would otherwise need a loop or an array: a 32-bit word becomes a set of up to 32 elements, and subset problems become counting from 0 to 2ⁿ − 1. It is examined in GATE (through two's complement arithmetic in Digital Logic and through C programming questions), in university Data Structures and Computer Organisation papers, and in almost every placement coding round — Amazon, Microsoft, Google India, Flipkart, Zoho, Goldman Sachs and Morgan Stanley all ask XOR and bitmask questions. On the job it is unavoidable in embedded and systems work (Qualcomm India, Bosch, Texas Instruments India, Tata Elxsi, ISRO), in networking (subnet masks) and in competitive programming.

Explained

Binary representation and two's complement

• An int is a fixed-width word: 32 bits in C/C++ (typical) and 32 bits in Java; 64 bits for long long in C/C++ and for long in Java (C/C++ long is 32-bit on Windows, 64-bit on Linux). Python integers are arbitrary precision and have no fixed width.
• Bits are numbered from 0 (least significant, value 2⁰) upward. Bit *i* of *x* has value 2ⁱ if set.
• Two's complement stores negatives as −x = ~x + 1, so one adder serves both addition and subtraction and there is a single zero. An n-bit signed range is −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1; for 32 bits, −2,147,483,648 to 2,147,483,647.
• The most significant bit is the sign bit: x < 0 is equivalent to ((x >> 31) & 1) == 1 for a 32-bit int.
• Consequence used constantly: -x leaves the lowest set bit of *x* and all the zeros below it unchanged, and inverts everything above it — which is why x & -x isolates the lowest set bit.
• INT_MIN is its own negation (overflow), so abs(INT_MIN) is undefined behaviour in C/C++ and Math.abs(Integer.MIN_VALUE) returns a negative number in Java.

The operators and the four basic bit operations

• Test bit i: (x >> i) & 1, or (x & (1 << i)) != 0.
• Set bit i: x |= (1 << i). Clear bit i: x &= ~(1 << i). Toggle bit i: x ^= (1 << i).
• Extract the low k bits: x & ((1 << k) - 1). Extract a field of width w starting at bit p: (x >> p) & ((1 << w) - 1).
• x << k equals x × 2^k only while the result fits; overflow of a signed left shift is undefined behaviour in C/C++. x >> k equals ⌊x / 2^k⌋ — note this *floors*, so -21 >> 2 is −6 while -21 / 4 is −5 in C and Java.
• Shifting by a count ≥ the type width is undefined behaviour in C/C++; in Java the count is taken modulo 32 (or 64 for long), so 1 << 32 evaluates to 1.

XOR: the properties that generate the question family

• Identities: x ^ 0 = x, x ^ x = 0, XOR is commutative and associative. Therefore XOR of a list cancels every value that appears an even number of times.
• Single number (every element twice except one): XOR the whole array; the survivor is the answer. O(n) time, O(1) space — the reason it is asked instead of hashing.
• Missing number in 0…n: XOR all indices and all values; everything pairs off except the missing one.
• Two single numbers (all others twice): XOR everything to get d = a ^ b; take bit = d & -d (a bit where *a* and *b* differ); partition the array by that bit and XOR each half separately.
• Every element thrice except one: maintain two accumulators, ones = (ones ^ x) & ~twos; twos = (twos ^ x) & ~ones; — a 2-bit per-position counter mod 3. The general form counts mod k using ⌈log2 k⌉ accumulators.
• Swap without a temporary: a ^= b; b ^= a; a ^= b; — correct only if a and b are different objects; if they alias, both become 0.
• Prefix XOR: pre[i] = a[0]^…^a[i-1], so the XOR of a subarray (l, r) is pre[r+1] ^ pre[l] — the XOR analogue of prefix sums, used for "count subarrays with XOR = k" with a hash map.
• Parity of a word = XOR of all its bits = popcount(x) & 1; computed by folding x ^= x >> 16; x ^= x >> 8; ….
• Gray code: g = n ^ (n >> 1) — consecutive codes differ in exactly one bit, used in rotary encoders and Karnaugh maps.

Counting and locating bits

• Brian Kernighan's algorithm: while (x) { x &= x - 1; count++; } runs once per *set* bit, so it is O(popcount) rather than O(width).
• Why x & (x-1) works: subtracting 1 flips the lowest set bit to 0 and all zeros below it to 1; ANDing keeps the higher bits unchanged and wipes that block.
• Built-ins (single instruction on modern CPUs): GCC/Clang __builtin_popcount, __builtin_popcountll, __builtin_ctz (trailing zeros = index of lowest set bit), __builtin_clz (leading zeros); C++20 std::popcount, std::countr_zero, std::bit_width in <bit>; Java Integer.bitCount, Integer.numberOfTrailingZeros, Integer.highestOneBit, Integer.reverse; Python bin(x).count('1'), or int.bit_count() from Python 3.10 and x.bit_length().
• __builtin_clz(0) and __builtin_ctz(0) are undefined — guard for zero.
• Counting set bits for all numbers 0…n (DP): dp[i] = dp[i >> 1] + (i & 1) or dp[i] = dp[i & (i-1)] + 1, both O(n).
• Useful idioms: x & -x isolates the lowest set bit; x | (x+1) sets the lowest zero bit; x & (x+1) clears all trailing ones; ~x & (x+1) isolates the lowest zero bit; x | (x-1) sets all bits below the lowest set bit.
• Power of two: x > 0 && (x & (x-1)) == 0. Next power of two ≥ x: 1 << (32 - __builtin_clz(x-1)) for x > 1.
• Branchless tricks: abs(x) as m = x >> 31; (x ^ m) - m; opposite signs as (x ^ y) < 0; min(a,b) as b ^ ((a ^ b) & -(a < b)).
• **Addition without +:** while (b) { carry = a & b; a = a ^ b; b = carry << 1; } — XOR is the sum bit, AND is the carry.

Bitmasks: sets, subsets and bitmask DP

• A mask of n bits represents a subset of an n-element universe: bit *i* set means element *i* is in the set. Natural for n up to about 20–25.
• Set operations become single instructions: union a | b, intersection a & b, difference a & ~b, symmetric difference a ^ b, membership (a >> i) & 1, size popcount(a), complement ((1 << n) - 1) ^ a.
• Enumerate all subsets: for (int m = 0; m < (1 << n); m++) — 2ⁿ masks.
• Enumerate all submasks of m: for (int s = m; s; s = (s-1) & m) then handle s = 0 separately. Over all masks this costs 3ⁿ in total, not 4ⁿ — each element is in the submask, in m-but-not-submask, or outside.
• Bitmask DP stores a state as (set of items already used, extra info). Standard problems: travelling salesman dp[mask][i] in O(2ⁿ · n²) time and O(2ⁿ · n) space; assignment of n jobs to n workers in O(2ⁿ · n); counting Hamiltonian paths; "minimum number of groups" partition DP in O(3ⁿ).
• Sum over subsets (SOS DP): for each bit, for (m) if (m >> i & 1) f[m] += f[m ^ (1 << i)]; gives, in O(n · 2ⁿ), the aggregate over every submask.
• Gosper's hack — next integer with the same popcount: c = x & -x; r = x + c; next = (((r ^ x) >> 2) / c) | r; — used to enumerate all k-subsets in increasing order.
• **std::bitset<N>** packs N bits into words, supports &, |, ^, count(), _Find_first(), and gives roughly a 64× constant-factor speedup and an 8× memory saving over bool[].

Language-specific behaviour and pitfalls

• Operator precedence is the single most common bug: &, |, ^ bind *looser* than == and != in C, C++ and Java, so if (x & 1 == 0) is parsed as if (x & (1 == 0)). Always bracket: if ((x & 1) == 0).
• Use 1LL << k (C/C++) or 1L << k (Java) when k ≥ 31; 1 << 31 on a 32-bit int overflows into the sign bit.
• Unsigned types wrap predictably and are the safe choice for pure bit work; mixing signed and unsigned in a comparison converts the signed value to unsigned and can invert the result.

Advantages, limits and complexity

• Advantages: O(1) set operations on up to 64 elements; constant memory for problems that otherwise need a hash set; cache-friendly dense storage; avoids branches, which helps the pipeline.
• Limits: masks are practical only to about n = 25 (2²⁵ ≈ 33.5 million states); the code is hard to read and easy to get wrong; micro-tricks rarely beat a modern optimising compiler on ordinary arithmetic; behaviour differs across languages and widths, so bit code ports badly.
• Complexity note: bit tricks change the *constant factor*, not usually the asymptotic class — except in bitmask DP, where they convert a factorial search into an exponential one (14! ≈ 8.7 × 10¹⁰ versus 2¹⁵ · 15² ≈ 7.4 × 10⁶).

Key points

• Two's complement - −x = ~x + 1; the sign bit is the MSB; the n-bit signed range is −2ⁿ⁻¹ … 2ⁿ⁻¹ − 1.
• Test / set / clear / toggle - (x>>i)&1, x|(1<<i), x&~(1<<i), x^(1<<i).
• **x & (x-1)** - clears the lowest set bit; zero result (with x > 0) means a power of two.
• **x & -x** - isolates the lowest set bit; the basis of Fenwick trees and of splitting on a differing bit.
• XOR cancels pairs - x^x = 0, x^0 = x; the whole "single number / missing number" family follows.
• Brian Kernighan - popcount in O(number of set bits), not O(width).
• Built-in popcount/ctz/clz - map to one CPU instruction; ctz(0) and clz(0) are undefined.
• Shift as arithmetic - x<<k = x·2^k, x>>k = ⌊x/2^k⌋ (floors, so it differs from / for negatives).
• Mask of k ones - (1<<k) - 1; use 1LL<<k for k ≥ 31.
• Subsets of n elements - 2ⁿ masks; iterate m = 0 … (1<<n)-1.
• Submask loop - for (s = m; s; s = (s-1) & m); total cost over all masks is 3^n.
• Bitmask DP - TSP and assignment in O(2ⁿ · n²) / O(2ⁿ · n), viable to n ≈ 20.
• Gray code - n ^ (n>>1); successive values differ in one bit.
• Hamming distance - popcount(x ^ y).
• Precedence trap - &, ^, | are looser than ==; always parenthesise.
• **Java >> vs >>>** - arithmetic versus logical shift; Python has no >>>, mask with 0xFFFFFFFF instead.
• **bitset<N>** - 8× less memory than bool[] and a ~64× constant-factor speedup on set operations.
• XOR 1…n has period 4 - n, 1, n+1, 0 for n mod 4 = 0, 1, 2, 3.

Formulas and examples

Example 1 — bit surgery and two's complement. Let x = 183 = 1011 0111.

• Bits set: 7, 5, 4, 2, 1, 0 → 128 + 32 + 16 + 4 + 2 + 1 = 183. ✔
• Test bit 3: (183 >> 3) & 1 = 10110 & 1 = 22 & 1 = 0 (clear).
• Set bit 3: 183 | 8 = 191. Clear bit 5: 183 & ~32 = 183 − 32 = 151. Toggle bit 0: 183 ^ 1 = 182.
• High nibble: (183 >> 4) & 0xF = 11 & 15 = 11 (0xB). Low nibble: 183 & 15 = 7.
• Two's complement of −20 in 32 bits: 20 = …0001 0100; invert → …1110 1011; +1 → …1110 1100 = 0xFFFFFFEC (= 2³² − 20 = 4,294,967,276 read as unsigned).
• -21 >> 2 = −6 (floor of −5.25) whereas -21 / 4 = −5 in C and Java — a classic off-by-one when a shift replaces a division.

Example 2 — popcount by Brian Kernighan, and Hamming distance. x = 156 = 1001 1100.

• popcount(156) = 4 in 4 iterations, not 8. 156 & -156 = 4 (lowest set bit, bit 2). 156 is not a power of two since 156 & 155 = 152 ≠ 0; 1024 & 1023 = 0, so 1024 is.
• Hamming distance between 29 (11101) and 23 (10111): XOR = 01010 = 10, popcount = 2 bits.

Example 3 — the two single numbers. Array [2, 4, 7, 9, 2, 4]; every value appears twice except 7 and 9.

1. XOR all: 2⁴ = 6; 6⁷ = 1; 1⁹ = 8; 8² = 10; 10⁴ = 14. So d = 14 = 1110 = 7 ^ 9. ✔
2. Lowest set bit: 14 & -14 = 2 (bit 1).
3. Partition on bit 1 — set: {2 (0010), 7 (0111), 2}; clear: {4 (0100), 9 (1001), 4}.
4. XOR each group: 2⁷² = 7; 4⁹⁴ = 9. Answer {7, 9}, in O(n) time and O(1) space.
5. Cross-check with the period-4 rule: XOR of 1…10, with 10 mod 4 = 2, should be 11. Longhand: 1² = 3, ³ = 0, ⁴ = 4, ⁵ = 1, ⁶ = 7, ⁷ = 0, ⁸ = 8, ⁹ = 1, ¹⁰ = 11. ✔

Example 4 — subset enumeration with a mask. Set {5, 9, 12}, n = 3, so 2³ = 8 masks.

• Subsets with sum ≥ 20: masks 6 and 7 → 2 subsets. Submasks of mask 6 (110): s = 6, then (6−1)&6 = 4, then (4−1)&6 = 2, then (2−1)&6 = 0 → stop → {6, 4, 2} plus the empty mask = 4 submasks = 2^popcount(6) = 2² = 4. ✔

Example 5 — why bitmask DP is worth the ugliness (TSP, n cities).

• At n = 15 the DP is about 11,800× fewer operations; at n = 20 it is still feasible (≈4 × 10⁸ transitions, ~21 M states), while brute force is not.
• Memory parallel: marking 10⁸ numbers with bool[] costs 100 MB; a bitset costs 10⁸ / 8 = 12.5 MB — the reason large sieves use bitsets.

// idiom sheet
bool isPow2(unsigned x) { return x && !(x & (x - 1)); }
int lowbit(int x)       { return x & -x; }
int popcnt(int x)       { int c = 0; while (x) { x &= x - 1; ++c; } return c; }
int gray(int n)         { return n ^ (n >> 1); }
// all submasks of m, including 0
for (int s = m; ; s = (s - 1) & m) { use(s); if (!s) break; }

Where it is used

• Embedded and VLSI firms (Bosch, Texas Instruments India, Qualcomm India, Tata Elxsi, L&T Technology Services, ISRO/DRDO labs): writing and reading microcontroller registers — GPIOA->ODR |= (1 << 5) to set a pin, &= ~ to clear — and packing sensor fields into CAN frames.
• Networking and cloud infrastructure: IPv4 subnet masks and CIDR (/24 is 0xFFFFFF00), computing a network address as ip & mask and broadcast as ip | ~mask; flags in TCP headers; used daily by network and SRE roles at Jio, Airtel, Cisco India and TCS/Infosys infra teams.
• Databases, search and analytics: roaring bitmaps and bitmap indexes for filtering, Bloom filters for membership tests, compressed inverted indexes at Flipkart, Swiggy, Zomato and Sprinklr-type product teams.
• Permissions and feature flags: Unix chmod octal modes are three 3-bit fields; application role masks and entitlement bits in banking backends (Goldman Sachs, Morgan Stanley, JPMorgan Chase technology centres in India).
• Competitive programming and hiring tests: bitmask DP and XOR problems on Codeforces, CodeChef and ICPC, and in the DSA rounds of Amazon, Microsoft, Google, Adobe, Zoho, Directi/Media.net and Arcesium.
• Graphics, compression and cryptography: colour channel packing (0xRRGGBB), Huffman and arithmetic coding bit streams, parity and CRC in storage, and the XOR/rotate/shift core of block ciphers and hash functions.

Interview questions

• Q: How do you check whether a number is a power of two in O(1)? A: x > 0 && (x & (x - 1)) == 0 — a power of two has exactly one set bit, and subtracting 1 flips that bit and sets all lower bits, so the AND is zero. The x > 0 guard excludes 0 and negatives.
• Q: Why does x & -x give the lowest set bit? A: In two's complement, -x = ~x + 1, which leaves the bits below and including the lowest set bit unchanged in value and inverts everything above it, so only that one bit survives the AND.
• Q: An array has every element twice except one. Find it in O(1) space. A: XOR all elements; equal values cancel because a ^ a = 0, leaving the unique element.
• Q: Extend that to exactly two unique elements. A: XOR everything to get d = a ^ b, take any set bit of d (use d & -d), split the array by that bit and XOR each half — a and b must fall into different halves.
• Q: Count set bits faster than looping over 32 positions. A: Brian Kernighan's x &= x - 1 loop runs once per set bit, or use a single-instruction built-in such as __builtin_popcount / Integer.bitCount / std::popcount.
• Q: What is the difference between >> and >>> in Java? A: >> is arithmetic and copies the sign bit, so -8 >> 1 is −4; >>> is logical and fills with zeros, so -8 >>> 1 is 2,147,483,644. C and C++ have no >>>; use an unsigned type.
• Q: Is x >> 1 always the same as x / 2? A: No. The shift floors, division truncates towards zero, so for x = -7 the shift gives −4 and the division gives −3. They agree only for non-negative x.
• Q: How do you enumerate every subset of a set of size n, and every subset of a given subset? A: Loop masks 0 to 2ⁿ − 1 for all subsets; for submasks of m use for (s = m; s; s = (s-1) & m) plus the empty mask, which costs 3ⁿ summed over all m.
• Q: Why is bitmask DP limited to about 20 elements? A: The state space is 2ⁿ (times n for a TSP-style second index), so n = 20 is already ~21 million states and n = 25 is ~840 million — memory, not time, usually fails first.
• Q: Swap two numbers without a temporary. What can go wrong? A: a ^= b; b ^= a; a ^= b; works, but if a and b are the same memory location both become 0, and in C a ^= b ^= a ^= b; is undefined behaviour because the object is modified twice without a sequence point.
• Q: What does x & (x + 1) do, and x | (x + 1)? A: x & (x + 1) clears all trailing 1 bits; x | (x + 1) sets the lowest 0 bit.
• Q: How would you compute a + b using only bitwise operators? A: Loop: sum = a ^ b (addition without carry), carry = (a & b) << 1, repeat with a = sum, b = carry until carry is 0.
• Q: Find the single element where every other appears three times. A: Keep two bitmasks acting as a mod-3 counter per bit: ones = (ones ^ x) & ~twos; twos = (twos ^ x) & ~ones; — ones holds the answer at the end.

Common mistakes

• Writing if (x & 1 == 0) instead of if ((x & 1) == 0) — == binds tighter than &, so the condition becomes x & 0, always false.
• Using 1 << i when i can be 31 or more on a 32-bit int: it overflows into the sign bit or is undefined; use 1LL << i (C/C++) or 1L << i (Java).
• Assuming x >> k equals x / 2^k for negative x, or assuming that shifting by the word width or more gives 0 — it is undefined behaviour in C/C++ and wraps modulo 32/64 in Java.
• Calling __builtin_ctz / __builtin_clz on 0, or relying on Math.abs(Integer.MIN_VALUE) and abs(INT_MIN) — all are undefined or wrong.
• Treating Python's ~x or x >> k as fixed-width: Python integers are unbounded and ~5 is −6, so 32-bit behaviour must be simulated with & 0xFFFFFFFF and a sign correction.
• Forgetting the empty submask: the loop for (s = m; s; s = (s-1) & m) silently skips s = 0.
• Reaching for bit tricks where they do not help — micro-optimising ordinary arithmetic that the compiler already handles, at the cost of unreadable code, instead of reserving bit work for sets, flags and masks.

Related topics

Number theory for programmers · Dynamic programming · Recursion and backtracking · Time and space complexity · DSA interview patterns · Searching and binary search