↓Skip to main content
  1. References/
  2. Algo Reference/
  3. Canonicals/

Topic 17: Bit Manipulation

·· 3649 words· 18 mins
Table of Contents

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

Canonical Questions #

XOR and Unique Element Detection #

  • Problems that use XOR to isolate single numbers or pairs

Problems #

  1. 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

       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

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

           return res
    Code Snippet 1: Single Number (136)
    Pattern Extraction

    Core Insight: XOR of all elements cancels out pairs (a ^ a = 0), leaving only the unpaired element. Identity: 0 ^ a = a. Pattern Name: XOR Cancellation for Singleton Detection Canonical Section: Bit Manipulation > XOR Properties Recognition Signals:

    • “Every element appears twice except one” – find the one
    • \(O(1)\) space required
    • XOR is associative and commutative (order doesn’t matter)

    Anti-Signals:

    • Every element appears THREE times except one – XOR doesn’t cancel triples. Need bit counting modulo 3. Connects to LC 137
    • TWO elements appear once – XOR gives their XOR, not their individual values. Need to split by a distinguishing bit. Connects to LC 260

    Decision Point: Pairs cancel with XOR. Triples cancel with bit counting mod 3. Two singletons = XOR all, then split groups by any set bit in the XOR result.

    Pitfalls and Misconceptions
    1. Trap: Using a hash set or Counter instead of XOR. Why: Works but uses \(O(n)\) space. XOR achieves \(O(1)\) space. Correction: result = 0; for num in nums: result ^ num; return result=.
    Problem Mutations
    1. What if every element appeared three times except one? (stress-tests: pair cancellation) XOR doesn’t cancel triples. Count each bit position modulo 3. Connects to LC 137 Single Number II.
    2. What if there were two unique elements? (stress-tests: single unique) XOR all to get a ^ b. Find any set bit (it distinguishes a from b). Split nums into two groups by that bit and XOR each group. Connects to LC 260 Single Number III.
    3. What if the array were sorted? (stress-tests: unsorted) Binary search for the point where pairs break: nums[2i] = nums[2i+1]= before the singleton, breaks after. \(O(\log n)\). Connects to LC 540.
    AI usage disclosure Claude Opus 4.6 · content enrichment
    Standardised annotation dropdowns for Single Number generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
  1. TODO Single Number II (137)
  2. TODO Single Number III (260)

Bitwise Transformations and Masks #

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

Problems #

  1. 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
    Code Snippet 2: Reverse Bits (190)
    Pattern Extraction

    Core Insight: Process each bit from the input: extract the lowest bit with n & 1, shift it into the result, shift n right. Repeat 32 times. Pattern Name: Bit-by-Bit Processing Canonical Section: Bit Manipulation > Bitwise Transformations Recognition Signals:

    • “Reverse bits” of a 32-bit integer
    • Process all 32 bits including leading zeros

    Anti-Signals:

    • Reverse decimal digits – modular arithmetic, not bit manipulation

    Decision Point: Bit reversal = 32 iterations extracting and placing bits.

    Pitfalls and Misconceptions
    1. Trap: Stopping when n = 0= instead of processing all 32 bits. Why: Leading zeros in the input become trailing zeros in the output. Stopping early drops them. Correction: Loop exactly 32 times.
    Problem Mutations
    1. What if the integer were 64-bit? (stress-tests: 32-bit) Loop 64 times instead of 32. Same algorithm.
    AI usage disclosure Claude Opus 4.6 · content enrichment
    Batch annotation for Reverse Bits.

  2. 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
    Code Snippet 3: Reverse Integer (7)
    Pattern Extraction

    Core Insight: Extract the last digit with x % 10, build the reversed number with result * 10 + digit. Check for 32-bit overflow before each multiplication. Pattern Name: Digit-by-Digit Reversal with Overflow Check Canonical Section: Bit Manipulation > Arithmetic Manipulation Recognition Signals:

    • “Reverse an integer”
    • Must handle 32-bit overflow (return 0 if overflow)
    • Handle negative numbers

    Anti-Signals:

    • Reverse bits, not digits – different problem (LC 190)

    Decision Point: The overflow check is the only tricky part. In Python, integers don’t overflow, so manually check against \(2^{31} - 1\) and \(-2^{31}\).

    Pitfalls and Misconceptions
    1. Trap: Not checking for 32-bit overflow. Why: The reversed number might exceed 32-bit integer range. Must return 0 in that case. Correction: Before result = result * 10 + digit, check if result > (2**31 - 1) // 10.
    2. Trap: Getting negative number modulo wrong in Python. Why: Python’s % is floor-based: -123 % 10 = 7=, not -3. Need int(x / 10) for truncation toward zero. Correction: Use digit = abs(x) % 10 and track sign separately.
    Problem Mutations
    1. What if the result needed to be a string? (stress-tests: integer output) Simpler: convert to string, reverse, convert back.
    2. What if overflow should wrap around instead of returning 0? (stress-tests: overflow = 0) Apply modular arithmetic: result % 2**32=.
    AI usage disclosure Claude Opus 4.6 · content enrichment
    Batch annotation for Reverse Integer.

  3. 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
    Code Snippet 4: Number of 1 Bits (191)
    Pattern Extraction

    Core Insight: Count set bits using n & (n-1) which clears the lowest set bit. Count iterations until \(n = 0\). Pattern Name: Brian Kernighan’s Bit Counting Canonical Section: Bit Manipulation > Bit Counting Recognition Signals:

    • “Count 1 bits” or “Hamming weight”
    • \(O(k)\) where \(k\) = number of set bits

    Anti-Signals:

    • Need to count bits for ALL numbers 0 to \(n\) – DP. Connects to LC 338

    Decision Point: Single number = Kernighan’s or bin(n).count('1'). Range of numbers = DP with dp[i] = dp[i >> 1] + (i & 1).

    Pitfalls and Misconceptions
    1. Trap: Using n >> 1= in a loop (checking each of 32 bits). Why: Works but is always 32 iterations. Kernighan’s is \(O(k)\) where \(k\) = set bit count. Correction: while n: n & n - 1; count += 1=. Each iteration removes one set bit.
    Problem Mutations
    1. What if you needed popcount for all numbers 0 to \(n\)? (stress-tests: single number) DP: dp[i] = dp[i >> 1] + (i & 1). Connects to LC 338.
    AI usage disclosure Claude Opus 4.6 · content enrichment
    Batch annotation for Number of 1 Bits.

  4. 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
    Code Snippet 5: Counting Bits (338)
    Pattern Extraction

    Core Insight: DP: dp[i] = dp[i >> 1] + (i & 1). The number of set bits in \(i\) equals the number in \(i/2\) (right-shifted) plus the last bit. Pattern Name: Bit Count DP with Right Shift Recurrence Canonical Section: Bit Manipulation > Bit Counting Recognition Signals:

    • “Count 1 bits for all numbers 0 to \(n\)”
    • \(O(n)\) time, \(O(n)\) space

    Anti-Signals:

    • Single number – just use Kernighan’s (LC 191)

    Decision Point: Range of numbers = DP. Single number = Kernighan’s.

    Pitfalls and Misconceptions
    1. Trap: Computing popcount independently for each number (\(O(n \log n)\) total). Why: Each popcount is \(O(\log n)\). The DP recurrence gives \(O(1)\) per number, \(O(n)\) total. Correction: dp[i] = dp[i >> 1] + (i & 1).
    Problem Mutations
    1. What if you needed the number with the maximum popcount in [0, n]? (stress-tests: all popcounts) Compute dp array, return argmax. Or directly: the number with all bits set up to \(\lfloor \log_2 n \rfloor\).
    AI usage disclosure Claude Opus 4.6 · content enrichment
    Batch annotation for Counting Bits.

  5. Power of Two (231)

  6. Power of Four (342)

Bit Shift, Rotate, and Gray Code #

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

Problems #

  1. Reverse Bits (190) – see solution above under Bitwise Transformations and Masks
  2. TODO Gray Code (89)
  3. TODO Rotate Function (396)

Counting and Parity Problems #

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

Problems #

  1. Counting Bits (338) – see solution above under Bitwise Transformations and Masks
  2. 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 #

  1. 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
    Code Snippet 6: Missing Number (268)
    Pattern Extraction

    Core Insight: XOR all numbers 0 to \(n\) with all numbers in the array. Pairs cancel, leaving the missing number. Alternatively: expected sum minus actual sum. Pattern Name: XOR Cancellation or Sum Difference Canonical Section: Bit Manipulation > XOR Properties Recognition Signals:

    • Array of \(n\) numbers from \([0, n]\) with exactly one missing
    • \(O(1)\) space required

    Anti-Signals:

    • Multiple numbers missing – need set difference or counting sort
    • Numbers aren’t from a known range – can’t use expected sum/XOR

    Decision Point: XOR is overflow-safe. Sum approach is simpler but can overflow in languages without arbitrary precision.

    Pitfalls and Misconceptions
    1. Trap: Using a set and scanning for the missing value (\(O(n)\) space). Why: Violates \(O(1)\) space. Correction: XOR or sum trick: \(O(1)\) space.
    Problem Mutations
    1. What if two numbers were missing? (stress-tests: single missing) XOR gives a ^ b. Split by any set bit. Same as LC 260.
    2. What if the range were \([1, n]\) instead of \([0, n]\)? (stress-tests: range bounds) Adjust expected sum/XOR. Same algorithm.
    AI usage disclosure Claude Opus 4.6 · content enrichment
    Standardised annotation dropdowns for Missing Number generated via batch canonical enrichment pass.

  2. TODO Find the Duplicate Number (287)

  3. 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)
    Code Snippet 7: Sum of Two Integers (371)
    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:

    1. 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).

    2. 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.

    Pattern Extraction

    Core Insight: a ^ b gives the sum without carries; (a & b) << 1 gives the carries. Repeat until carries are zero. Pattern Name: Bitwise Addition (Half-Adder Loop) Canonical Section: Bit Manipulation > Arithmetic via Bits Recognition Signals:

    • “Add two numbers without + or - operators”
    • Bitwise operations only
    • Iterative carry propagation

    Anti-Signals:

    • Subtraction – use two’s complement: a - b = a + (~b + 1)
    • Multiplication – shift-and-add

    Decision Point: Bitwise addition = XOR (partial sum) + AND-shift (carry). This is how hardware adders work.

    Pitfalls and Misconceptions
    1. Trap: Infinite loop in Python due to arbitrary-width integers. Why: Python integers have unlimited precision. Negative numbers have infinite leading 1s, so the carry never becomes zero. Correction: Mask to 32 bits: a & 0xFFFFFFFF= after each operation. Check sign at the end.
    Problem Mutations
    1. What if you needed subtraction? (stress-tests: addition) a - b = a + (~b + 1). Use the same bitwise addition on a and the two’s complement of b.
    2. What if you needed multiplication? (stress-tests: operation type) Shift-and-add: for each set bit in b, add a << bit_position to the result.
    AI usage disclosure Claude Opus 4.6 · content enrichment
    Standardised annotation dropdowns for Sum of Two Integers generated via batch canonical enrichment pass.

Bitwise Ranges and Interval Operations #

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

Problems #

  1. Bitwise AND of Numbers Range (201)
  2. XOR Operation in an Array (1486)

Bitmask DP and Enumeration / State Compression #

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

Problems #

  1. Partition to K Equal Sum Subsets (698)
  2. Maximum Product of Word Lengths (318)
  3. (Any subset/visited DP problem)

Maximum XOR/Bit Logic Optimization #

  • Optimising with tries or greedy for maximal bitwise value/combinations

Problems #

  1. Maximum XOR of Two Numbers in an Array (421)

  2. 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
    Code Snippet 8: Maximum XOR of Two Numbers in an Array (421)

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).

    more elaboration

    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.

Decision Flow #

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

Styles, Tricks and Boilerplate #

Styles #

Tricks #

Boilerplate #

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;
    Code Snippet 9: Numbers:

    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:

  1. [best] use the builtin: n.bit_count() # where n is an int

    this needs python 3.10+

  2. [old] stringify then count 1s: bin(n).count('1')

  3. [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
    Code Snippet 10: Counting set bits for popcount aka Hamming Weight:

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
Code Snippet 11: Iterate over all subsets of a bitmask:

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

  • Uses:

    1. 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

    2. 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
      Code Snippet 12: Using n & (n - 1) to remove LSB (Brian Kernighan’s algorithm)

  1. 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 #

See XOR and Unique Element Detection above for the Single Number (136) solution.

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
Code Snippet 13: 268. Missing Number | LeetCode

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

TODO KIV #