Bit Manipulation

Notes and typical questions for bits related problems

Notes

• Binary to Decimal Conversion

  • $1101_2$ $=1*2^3 + 0*2^2 + 1*2^1 + 1*2^0$ $=8+0+2+1=11$

• Java int is 32 bits.

• Get the last bit of an int number: int bit = n&1

• Bit operation precedence is kind of low. Protect it with ()

• XOR (exclusive OR)

  • Rules

    • 0 ^ a = a

    • a ^ a = 0

    • a ^ b ^ c = a ^ c ^ b

  • Use cases

    • Swap 2 var without temp var

      int x = 10, y = 20;
      x = x ^ y;  // x becomes 30 (binary XOR of 10 and 20)
      y = x ^ y;  // y becomes 10 (original value of x)
      x = x ^ y;  // x becomes 20 (original value of y)

    • Find a Single Number in an Array. There are some special requirements on the array.

• Two's complementary (二进制补码)

  • In Java (and most modern systems), negative numbers are stored in two’s complement format.

    • If n is an integer, -n = ~n+1 . In this way, -n+n will have zero in all bits

  • Also, based on this, n&(-n) is a way to keep the rightmost 1-bit and to set all the other bits to 0.

Typical Questions

• 🌟 LC 191. Number of 1 Bits

  • Approach 1: Use mask&n to check each bit in for loop.

    • Answer. TC: $O(1)$, SC: $O(1)$

  • 👍 🟠 Approach 2: Bit Manipulation. Subtracting 1 from n flips all the bits to the right of the least significant 1 bit (including the 1 itself). Then performing n & (n - 1) clears that least significant 1.

    • Answer.

      • TC: $O(log{n})$, where $log{n}$ is the maximum number of bits in a number

      • SC: $O(1)$

• 🟠 LC 38. Counting Bits

  • It can be resolved by DP

  • Optimal Answer.

    • TC: $O(n)$

    • SC: $O(n)$

• 🟠 LC 136. Single Number

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

• 🟠 LC 137. Single Number II

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

  • Reference: https://leetcode.com/problems/single-number-ii/solutions/43297/java-on-easy-to-understand-solution-easi-qoxr

• ⚪ LC 1318. Minimum Flips to Make a OR b Equal to c

  • Optimal Answer.

    • Let n be the maximum length in the binary representation of a, b or c

    • TC: $O(n)$

    • SC: $O(1)$

• 🟠 LC 231. Power of Two

  • Optimal Answer. TC: $O(1)$, SC: $O(1)$

• 🌟 🟠 LC 190. Reverse Bits

  • Optimal Answer. TC: $O(1)$, SC: $O(1)$

• 🟠 LC 201. Bitwise AND of Numbers Range

  • Optimal Answer. TC: $O(1)$, SC: $O(1)$

• 🔴 LC 751. IP to CIDR

  • Optimal Answer. Assume the output size is $k$, TC: $O(k)$, SC: $O(1)$

• 🟠 LC 2571. Minimum Operations to Reduce an Integer to 0

  • Optimal Answer. TC: $O(logn)$, SC: $O(1)$

• 🟠 LC 2749. Minimum Operations to Make the Integer Zero

  • Optimal Answer. TC: $O(1)$, SC: $O(1)$