Bit Operations

Basics - True Form, Ones' Complement, Two's Complement

As we all know, the most fundamental element in computer programs is binary. Here are three types of codes you must understand about binary:

• True Form: The first bit is the sign bit, where 1 represents negative and 0 represents positive; The ones' complement and two's complement of positive numbers are the same as their true form
• Ones' Complement: For negative numbers, the sign bit is 1, and all other bits are inverted (0->1, 1->0)
• Two's Complement: For negative numbers, it's their ones' complement + 1

The principle of two's complement is modular congruence. Recommended reading: Computer Organization - True Form, Ones' Complement, Two's Complement. Integers exist in computers as two's complement because it makes negative number calculations easier.

Bit Operations

• &, AND: results in 0 if any bit is 0
• |, OR: results in 1 if any bit is 1
• ~, NOT: inverts all bits. Its decimal mathematical calculation is add 1 and invert
• ^, XOR: results in 0 if bits are the same, 1 if different
• x >> n, right shift: discards low bits, fills high bits with sign bit. Its decimal mathematical calculation is x / 2^n
• x << n, left shift: discards high bits, fills low bits with 0. Its decimal mathematical calculation is x * 2^n

Common Techniques

In the following, x represents a number

• Check if odd/even: x & 1 ? odd : even
• Round towards zero¹: x | 0
• Check indexOf result: !~x, only when x is -1, ~x equals 0, you can think of it as !(not)~(exists)x
• Convert boolean to 0/1: ~~x, true -> 1, false -> 0
• Middle value: x >> 1
• Check if numbers have opposite signs: (x ^ y) < 0 means opposite signs. The advantage over using multiplication is no integer overflow. Note that bit operations have lower precedence than arithmetic operations, so remember to add parentheses when combining them.

Advanced Techniques

• x & x - 1, eliminates the last 1 in x's binary representation.
  • Can be used to solve lc.191 Hamming Weight, lc.461 Hamming Distance, lc.231 Power of Two
• x & -x, gets the value represented by the last 1 in x.
  • In React source code, getHighestPriorityLane uses this to get the highest priority (React defines 1 as higher priority the more right it is).
• x ^ x === 0; x ^ 0 === x, and XOR operation satisfies commutative and associative laws.

Let's look at a classic problem: In a set of numbers, only 2 numbers appear once, while others appear an even number of times. Find these 2 numbers.

// test: [1,2,3,4,5,6,5,4,3,2]
function findOnlyOne(arr) {
  let val = 0
  for (const item of arr) {
    val ^= item
  }
  // At this point, val is the XOR result of the two numbers that appear only once
  // Based on XOR properties (same bits = 0, different bits = 1), two different numbers XORed will have at least one 1
  // We can find the rightmost 1
  const rightOne = val & -val

  let a = 0
  for (const item of arr) {
    // rightOne can divide the original data into two groups, thus separating the first different number
    if ((rightOne & item) === 0) {
      a ^= item
    }
  }
  let b = a ^ val // Using XOR property: if a ^ b = c, then a ^ c = b
  return [a, b]
}

In some source code, binary is often used to define constants, and bit operations are used for processing:

const A = 1 << 0; // 0b00000001
const B = 1 << 1; // 0b00000010
const C = 1 << 2; // 0b00000100

const ABC = A | B | C; // 0b00000111 add properties
const AB = ABC & ~C;   // 0b00000011 remove properties
(AB & B) === B         // true, means AB contains B
(AB & C) === 0         // true, means AB doesn't contain C

Recommended Reading

• Bit Twiddling Hacks