Topic 17: Bit Manipulation

Table of Contents

Key Intuition: Bit manipulation uses properties of binary representation to efficiently solve math and combinatorial problems.

Canonical Question Types #

XOR and Unique Element Detection #

Problems that use XOR to isolate single numbers or pairs

Problems #

Single Number (136)

We’re told that every number in the input has a corresponding pair except one of them and we are asked to find that one and immediately we know that we can exploit the commutative nature of XOR-ing and the fact that a number XORed with itself will give 0, and we just cumulatively XOR all elements to get our ans.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    class Solution:
        """
        Finds the element that appears only once in a list where each element appears twice, except for one.
        Uses XOR to cancel pairs.
        """

        def singleNumber(self, nums: List[int]) -> int:
            res = 0
            first_roun

            for num in nums:
                # num xor-ed with 0 will give itself, pairs will cancel out
                res ^= num

            return res

TODO Single Number II (137)
TODO Single Number III (260)

Bitwise Transformations and Masks #

Bit reversal, counting bits, setting, toggling, clearing, or checking specific bits

Problems #

Reverse Bits (190)

This is like a water pump where we take from one and send to another.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
    class Solution:
        def reverseBits(self, n: int) -> int:
            ans = 0
            for i in range(32):
                # this allows us to map the LSB (based on extract_idx) as the MSB (based on write_idx)
                extract_idx, write_idx = i, 31 - i
                bit = (n >> extract_idx) & 1
                ans |= bit << write_idx

            return ans

Reverse Integer (7)

This isn’t that bit manipulation heavy, just uses it for checking overflows and keeping the intermediates within 32-bit width

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
    class Solution:
        def reverse(self, x: int) -> int:
            # get min max from signed integers
            MAX, MIN = (2**31) - 1, -2**31

            is_negative = x < 0 # store sign in a flag
            x = abs(x)

            ans = 0
            while still_have_bits_to_strip:=x != 0:
                digit = x % 10
                x //= 10

                # check overflow before updating, only need to check against MAX since we work with the abs() number
                if ans > (MAX - digit) // 10:
                    return 0

                ans = ans * 10 + digit

            return -ans if is_negative else ans

Number of 1 Bits (191)

So this one has a “by the books” solution where we extract out the LSBs and count them. Alternatively, we can just use python.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    # python stdlib use
    class Solution:
        def hammingWeight(self, n: int) -> int:
            return n.bit_count()
    # stdlib use, count the 1s in the stringified version
    def hammingWeight(self, n: int) -> int:
        return bin(n).count('1')
    # iterative countingof LSBs
    class Solution:
        def hammingWeight(self, n: int) -> int:
            counter = 0
            while n != 0:
                n &= (n - 1)
                counter += 1

            return counter
    # bit masking approach
    def hammingWeight(self, n: int) -> int:
        count = 0
        for i in range(32):
            count += n & 1 # 1 if that bit is set, else 0
            n >>= 1 # right-shift for next consideration
        return count

Counting Bits (338)

There’s a bunch of ways to do this, the naive one being the use of the python stdlib and still getting an \(O(n)\) solution, but observing things reveals a DP-like approach where we can use the previous (rightshifted version of i) to build up the new entries.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

    # python stdlib use in O(n) time
    class Solution:
        def countBits(self, n: int) -> List[int]:
            return [i.bit_count() for i in range(n + 1)]

    # DP like approach:
    class Solution:
        def countBits(self, n: int) -> List[int]:
            # init dp with (n + 1)
            ans = [0] * (n + 1)

            for i in range(1, n + 1):
                # remove rightmost index's value and add 1 if it's actually a one that got extracted
                ans[i] = ans[i >> 1] + (i & 1)

            return ans

Power of Two (231)
Power of Four (342)

Bit Shift, Rotate, and Gray Code #

Left/right shifts, circular rotations, gray code constructions, popcount

Problems #

Reverse Bits (190)

This is like a water pump where we take from one and send to another.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
    class Solution:
        def reverseBits(self, n: int) -> int:
            ans = 0
            for i in range(32):
                # this allows us to map the LSB (based on extract_idx) as the MSB (based on write_idx)
                extract_idx, write_idx = i, 31 - i
                bit = (n >> extract_idx) & 1
                ans |= bit << write_idx

            return ans

TODO Gray Code (89)
TODO Rotate Function (396)

Counting and Parity Problems #

Counting set bits, parity checks, popcount, finding first/last set bits

Problems #

Counting Bits (338)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

    # python stdlib use in O(n) time
    class Solution:
        def countBits(self, n: int) -> List[int]:
            return [i.bit_count() for i in range(n + 1)]

    # DP like approach:
    class Solution:
        def countBits(self, n: int) -> List[int]:
            # init dp with (n + 1)
            ans = [0] * (n + 1)

            for i in range(1, n + 1):
                # remove rightmost index's value and add 1 if it's actually a one that got extracted
                ans[i] = ans[i >> 1] + (i & 1)

            return ans

Number of Steps to Reduce a Number to Zero (1342)

Missing / Special Number Bit Patterns #

Use bit patterns for missing/duplicated/unique number detection, alternative to hash/set logic

Problems #

Missing Number (268)

There’s an elegant math approach to this and then there’s the bitwise approach to this. For the math approach, it’s basically primary school pattern of using Gauss’ sum to our advantage. As for the bitwise operation, we’re using the same XOR commutative trick as we did for the single number I problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
    # GAUSS' SUM exploited
    class Solution:
        def missingNumber(self, nums: List[int]) -> int:
            n = len(nums)
            expected_sum = n * (n + 1) // 2
            actual_sum = sum(nums)
            return expected_sum - actual_sum

    # BITWISE XOR APPROACH
    from typing import List

    class Solution:
        def missingNumber(self, nums: List[int]) -> int:
            """
            Finds the missing number in [0, n] given an array of n unique numbers.
            Uses XOR operation to cancel out matching indices and array values.
            """
            n = len(nums)
            missing_num = n
            for i in range(n):
                missing_num ^= i ^ nums[i]
            return missing_num

    # I could have written it like so:
    class Solution:
        def missingNumber(self, nums: List[int]) -> int:
            res = 0

            for i in list(range(len(nums) + 1)) + nums:
                res ^= i

            return res

Find the Duplicate Number (287)

Sum of Two Integers (371)

This question is about taking 2 32-bit integers and summing them up without directly using the sum operator. the key trick here is to be able to realise that we need to do sums and we also need to figure out what to do with carry bits, and this is something we iterate and work with the partial sums.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    class Solution:
        def getSum(self, a: int, b: int) -> int:
            MASK = 0xFFFFFFFF # 32 bits integer mask
            MAX_INT = 0x7FFFFFFF # (2**31) - 1 in hex

            while has_carry_bits:=b != 0:
                sum_no_carry = (a ^ b) & MASK # keep it within 32 bits
                carry_bits = ((a & b) << 1) & MASK # shift all the carry bits to their carry positions
                a, b = sum_no_carry, carry_bits

            return a if a <= MAX_INT else ~(a ^ MASK)

this deserves a longer explanation:

We consider just a single bit, then we know that to sum up two bits, we need to handle the value in its place as well as the carry value.

We can handle them separately in 2 stages:

stage 1 partial sum (no carry): this is the sum of bits ignoring any carry a ^ b
we sum them without caring about the carry value
@ each bit position,
If both bits are different, sum bit = 1 (no carry).
If both bits are the same, sum bit = 0 (carry might be generated).

stage 2 carry bits: for bits that need to be added one position higher (a & b) << 1
we only care about the carry value and shift it
carry bit from \(i^{th}\) place goes to \(( i + 1 )^{th}\) place.

Now, to get the final sum, we have to add again the carry to the partial sum.

Assigning a = sum_no_carry sets up the new current sum without any leftover carry.
Assigning b = carry sets up the carry bits to be added in the next iteration.

The loop’s role is to keep combining until:

There are no more carry bits (i.e., b = 0=).
At this point, all carry bits have been accounted for, and a holds the full sum.

Bitwise Ranges and Interval Operations #

Bitwise AND/OR/XOR over a number range, interval-based bit logic

Problems #

Bitmask DP and Enumeration / State Compression #

Subset enumeration, DP or tracking state with bitmasks, combinatorial grouping, visited/state compression

Problems #

Maximum XOR/Bit Logic Optimization #

Optimizing with tries or greedy for maximal bitwise value/combinations

Problems #

Maximum XOR of Two Numbers in an Array (421)

Partition Array for Maximum XOR and AND (3630)

To be honest I have no idea what the heck this is.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
    class Solution:
        def maximizeXorAndXor(self, nums: List[int]) -> int:
            """
            Notes:
            1. Split nums into a B group and a not B group
            2. Let S be XOR of not B group
            3. XOR(A) + XOR(C) = X + (X ^ S) X is a subset XOR of not B group
            4. For a single bit:
                X and S => 1
                !X and !S => 0
                X and !S => 0 with 1 carry => equivalent to (~S & X) << 1
                => ~S & X
                !X and S => 1
                -> When S is set, output bit is set
                => Rewrite expression as S + (~S & X) << 1
                bcoz (S is set) + (S not set, X set) + (both not set == 0)
            5. Goal is to maximize (~S & X)
            6. By distributive property, max((~S & x1) ^ (~S & x2) ...)
            7. Create an XOR basis for the set of ~S & xn (this converts XOR to addition kinda)
               Also removes dependance allowing for next step
            8. Go through the elements in decreasing order and include those
               which increase the value
            """
            N = len(nums)
            ans = 0
            for mask in range(1 << N):
                S = 0
                B = None
                pos_basis = []
                for i in range(N):
                    if (1 << i) & mask:
                        if B is None: B = nums[i]
                        else: B &= nums[i]
                    else:
                        S ^= nums[i]
                        pos_basis.append(nums[i])

                pos_basis = [num & ~S for num in pos_basis]
                basis = []
                for num in pos_basis:
                    for b in basis:
                        num = min(num, num ^ b) # Subtract b from num if possible
                    if num: basis.append(num)

                basis.sort(reverse=True)
                X = 0
                for b in basis:
                    X = max(X, X ^ b)

                B = 0 if B is None else B
                ans = max(ans, B + S + ((~S & X) << 1))
            return ans

SOE #

Overflow or sign extension errors in shifts
Incorrect mask creation or usage
Misuse of bit operators (AND, OR, XOR)
When mapping LSB to MSB, (integers), mapping the extract_idx and the write_idx wrongly
GOTCHA: careful: When you take the bit at position i (starting from the right, 0-based), its reversed position is at 31 - i (from the left).
Here’s more elaboration on it:
GOTCHA: careful: When you take the bit at position i (starting from the right, 0-based), its reversed position is at 31 - i (from the left).
The reason for using 31 - i in the expression bit << (31 - i) when reversing bits of a 32-bit number is that the bits are being mirrored around the center of the 32-bit integer.
The integer has 32 bits indexed from 0 (least significant bit, rightmost) to 31 (most significant bit, leftmost).
Whenever you take the bit at position i (starting from the right, 0-based), its reversed position is at 31 - i (from the left).
This shifts the bit that was originally near the right end to the equivalent position near the left end, effectively reversing the bit order.
For example, if i = 0, you are taking the rightmost bit, which becomes the leftmost bit after reversal (position 31). If i = 31, you take the leftmost bit and move it to the rightmost position (0).

We also need to force out the max int behaviour (to account for negative numbers) and manage “overflows”. This is necessary because python is variable-widthed.

Firstly note that if we consider 32-bit integers, the mask to use is 0xFFFFFFFF (the largest int can only be (2 ** 31) - 1). Therefore, we have to check if our number should be represented as a negative number if there’s an “overflow”.

1
2
3
4
5
6
7
8
  MAX_INT = (2 ** 31) - 1
  a = MAX_INT + 2
  print(a)
  if a<= MAX_INT:
          a = a # this is the normal, positive value
  else:
          a = ~(a ^ 0x7FFFFFFF) # any bits more than 32 will become 0, so we effectively ignored them
  print(a)

here, if it’s overflown, then we flip all bits except the sign bit (that’s why it’s a ^ 0x7FFFFFFF which converts the lower 31 bits then we flip all bits using the ~)

Alternatively, we can do this to be more python-idiomatic

1
2
3
  a = a & 0xFFFFFFFF
  if a > 0x7FFFFFFF: # overflow, should be seen as negative
      a -= 0x100000000 # subtract 2 ** 32 to map it to python's negative integer space.

Recipes #

ASCII manipulations using bithacks #

The way ASCII encoding has been done using numerical code-points, the use of code points for spaces and underscores allow us to do these bit hacks:

convert English chars to lowercase using |
chr(ord('a') | ord(' ')) # gives 'a', no change
chr(ord('A') | ord(' ')) # gives 'a'; upper to lower
convert English chars to uppercase using & chr(ord('b') & ord(' ')) # gives 'B' make uppercase
chr(ord('B') & ord(' ')) # gives 'B' no change
toggle casing of English chars using ^ chr(ord('d') ^ ord(' ')) # gives 'D'; toggle lower to upper
chr(ord('D') ^ ord(' ')) # gives 'd' # toggle upper to lower

Numbers: #

Memory Manipulations
we can swap two integers without using a temporary variable.
1 2 3 4
a = 1, b = 2; a ^= b; b ^= a; a ^= b;
QQ: this seems to only be for integers, floats don’t work (this is because the bitwise XOR is not defined for floats, only for ints)
Incrementing / Decrementing: both of these work because the numbers in python are represented using 2s complement, which allows us to do some automatic arithmetic on it:
- to increment we do n = -~n the ~ flips every bit of n then the negation will add 1 to n; works because of the 2s-complement representation of numbers
- to decrement we do n = ~-n so -n computes the 2s-complement negative then taking the bitwise NOT subtracts 1 from n
comparing signs, is_opposite? using 2-s complement manipulations It utilizes the sign bit of two’s complement encoding.
The highest bit in integer encoding is the sign bit:
negative numbers have a sign bit of 1, non-negative numbers have a sign bit of 0.
Using the properties of XOR, you can determine if two numbers have opposite signs
- is_opposite = bool((x ^ y) < 0) # where x and y are two different numbers

check the \(N^{th}\) bit: (x >> n) & 1 right shift by n positions and check AND 1
set the \(N^{th}\) bit: x | (1 << n) left shift 1 by n positions and OR it with x
clear \(N^{th}\) bit: x & ~(1 << n) left shift 1 by n then flip it to be zero then use that to AND with x to clear the nth bit
toggle \(N^{th}\) bit: x ^ (1 << n) left shift 1 by n then xor it with x

Counting set bits for popcount aka Hamming Weight: #

There’s a bunch of ways to do popcount:

[best] use the builtin: n.bit_count() # where n is an int
this needs python 3.10+
[old] stringify then count 1s: bin(n).count('1')

[old, long] bitwise clear the lowest set bit iteratively:

1
2
3
4
5
6
   def popcount(x):
       c = 0
       while x:
           x &= x - 1
           c += 1
       return c

Lowest Set Bit: #

Get Lowest set bit: #

x & -x

Remove lowest set bit: #

x & (x - 1)

Iterate over all subsets of a bitmask: #

1
2
3
4
5
mask = some_mask
sub = mask
while sub:
    # use sub
    sub = (sub - 1) & mask

Using `n & (n - 1)` to remove LSB (Brian Kernighan’s algorithm) #

Uses:

Eliminating the last (LSB) 1 in the binary representation of number n
core logic is that n - 1 will always remove the last 1 and turn all trailing 0s into 1s. Then, performing the & operation with n will turn only the last 1 into 0

Calculating Hamming Weight (number of set bits)

This way of removing LSB is useful for counting hamming weight.

Keep removing MSB 1 until the whole number is 0.

However, there are better ways to get hamming weight in python (see sections above).

1
2
3
4
5
6
7
     class Solution:
         def hammingWeight(self, n: int) -> int:
             res = 0
             while n != 0:
                 n = n & (n - 1)
                 res += 1
             return res

Determine if a number is a power of 2

A number is a power of two if its binary representation contains only one ‘1’. So if we remove LSB 1, then it should be 0

1
2
3
4
5
6
     class Solution:
         def isPowerOfTwo(self, n: int) -> bool:
             if n <= 0:
                 return False

             return (n & (n - 1)) == 0

Using XOR with itself `a ^ a = 0` #

A number XORed with itself results in 0, i.e., a ^ a = 0; a number XORed with 0 results in itself, i.e., a ^ 0 = a

single number problem #

LeetCode Problem 136 “Single Number”

For this problem, XOR all the numbers.

Pairs of numbers will result in 0, and the single number XORed with 0 will still be itself.

Therefore, the final XOR result is the element that appears only once:

1
2
3
4
5
6
7
8
9
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0

        for num in nums:
            # num xor-ed with 0 will give itself, pairs will cancel out
            res ^= num

        return res

missing number problem #

268. Missing Number | LeetCode

the bithack version hinges on the fact that XOR is commutative and associative.

Consider adding an index and then to each element we have indices that correspond to its equal index:

After doing this, you can see that all indices and elements form pairs, except for the missing element. Now, if we find the single index 2, we find the missing element.

By XORing all elements and indices, paired numbers will cancel out to 0, leaving the single element, achieving our goal

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        # first XOR with the new added index
        res ^= n
        # XOR with other elements and indices
        for i in range(n):
            res ^= i ^ nums[i]
        return res

In some situations, a better alternative to modulo for making a circular array #

Style, Boilerplate #

Decision Flow #

Unique element problem? → XOR apply
Subset enumeration? → Bitmask DP
Bit counting or toggling? → Builtin functions or masks

Canonical Question Types #

XOR and Unique Element Detection #

Problems #

Bitwise Transformations and Masks #

Problems #

Bit Shift, Rotate, and Gray Code #

Problems #

Counting and Parity Problems #

Problems #

Missing / Special Number Bit Patterns #

Problems #

Bitwise Ranges and Interval Operations #

Problems #

Bitmask DP and Enumeration / State Compression #

Problems #

Maximum XOR/Bit Logic Optimization #

Problems #

SOE #

Recipes #

ASCII manipulations using bithacks #

Numbers: #

\(N^{th}\) bit related: #

Counting set bits for popcount aka Hamming Weight: #

Lowest Set Bit: #

Get Lowest set bit: #

Remove lowest set bit: #

Iterate over all subsets of a bitmask: #

Using n & (n - 1) to remove LSB (Brian Kernighan’s algorithm) #

Using XOR with itself a ^ a = 0 #

single number problem #

missing number problem #

In some situations, a better alternative to modulo for making a circular array #

Style, Boilerplate #

Decision Flow #

Using `n & (n - 1)` to remove LSB (Brian Kernighan’s algorithm) #

Using XOR with itself `a ^ a = 0` #