Bit Manipulation Notes

This note is primarily based on Explore Card on leetcode. And the objective is to grasp the basics of bit in computer science and tackle the related leetcode problems with confidence.

Concepts introduction

Base

Base is a carry counting system with fixed digital symbols and rules. We use decimal numeral system (base-10) as standard in everyday life.

In computer science, the binary system is mostly used. Octal (base-8) and hexadecimal (base-16) are also commonly used.

Conversion between bases

Non-decimal to decimal

Add the weighted sum of each digit.

$$750_{(8)}=7\times8^2 + 2\times8^1 + 0\times8^0 + 5\times8^{-1} = 464.625$$

Decimal to non-decimal

We convert the integer part and the fractional part separately. Divide it by X until it reaches 0, and record the remainder each time. Convert 50 in base-10 to base-2:

50 / 2 = 25; 50 % 2 = 0
25 / 2 = 12; 25 % 2 = 1
12 / 2 = 6 ; 12 % 2 = 0
6  / 2 = 3 ; 6  % 2 = 0
3  / 2 = 1 ; 3  % 2 = 1
1  / 2 = 0 ; 1  % 2 = 1

Traversing the remainder in reverse order, we get 1, 1, 0, 0, 1, 0, so 50 in decimal will become $110010_{(2)}$ in binary.

To convert the fractional part, we multiply the fractional part of the decimal number by X until it becomes 0 and record the integer part each time. To convert $0.6875$ to binary:

0.6875 * 2 = 1.375 with 1
0.375 * 2 = 0.75 with 0
0.75 * 2 = 1.5 with 1
0.5 * 2 = 1 with 1

Traversing the integer part in order, we get 1, 0, 1, 1, so $0.6875$ in decimal will become $0.1011_{(2)}$ in binary.

Conversion between other bases

The common practice is to convert to decimal first and then convert to the target base. But for binary to octal or hexadecimal, each digit in octal number can be represented as three digits in binary number, hexadecimal as four.

$1011110010_{(2)}$ -> 101|110|010 -> 1|0111|0010 -> $562_{(8)}$ , $172_{(16)}$.

Example problems

• 504. Base 7
• 405. Convert a Number to Hexadecimal (This requires complement number knowledge, mentioned below)

Original code, Inverse code, Complement code

The binary representation of a number in a computer is machine number. The machine number is a signed number, the highest bit is the sign bit, 0 for non-negative number, 1 for negative number.

Take 8-bit binary numbers as an example. $+10_{(10)}$ is $00001010_{(2)}$, and $-10_{(10)}$ is $10001010_{(2)}$. We can see that the value of machine number is not necessarily equal to its true value.

The range of values by original code of an 8-bit binary number is $-127$ to $+127$. This is the most straightforward by human brain, but it has two problems:

1. There’re $+0$ and $-0$, two different original codes corresponding to $0$.
2. Performing subtractions with the original code will lead to incorrect results. (Try your self)

• The original code of $+10$ is $00001010$, and the inverse code is $00001010$.
• The original code of $−10$ is $10001010$, and the inverse code is $11110101$.

The inverse code solves the problem of subtraction errors, but the issue of dual representation of $0$ remains. The complement code solves the both. Moreover, one more minimum value can be represented.

In complement code, there’s no $-0$, so we could have $-128$. The computer uses the complement code for calculations.

Bitwise operators

• For non-negative numbers, the arithmetic right shift and logical right shift are identical.
• In Java, >> means arithmetic right shift, >>> means logical right shift.

Relationship between shift and multiplication / division

All calculations in computers are implemented with bit operations, the efficiency of using shift operations is significantly higher than of directly using multiplication and division.

Left shifting a number by k bits is equivalent to multiplying the number by $2^k$. When the multiplier is not an integer power of 2, it can be split into the sum of two parts. a * 6 is equivalent to (a << 2) + (a << 1). Be careful with overflow.

Arithmetic right shifting a number by k is equivalent to dividing the number by $2^k$, but this is only true for non-negative number. The result is rounded down, but for negative numbers, (-50) >> 2 is $-13$, the valid result should be (-50) / 4 = -12.

Details

NOT

NOT: Bitwise NOT is a unary operator that flips the bits of the integer. If the current bit is 000, it will change it to 111 and vice versa. The symbol of the bitwise NOT operator is tilde (~).

N = 5 = 101 (in binary)
~N = ~(101) = 010 = 2 (in decimal)

AND

AND: If both bits in the compared position of the operand are 1, the bit in the resulting bit pattern is 1, otherwise 0. The symbol of the bitwise AND operator is ampersand (&).

A = 5 = 101 (in binary) 
B = 1 = 001 (in binary) 
A & B = 101 & 001 = 001 = 1 (in decimal)

OR

OR: If both bits in the compared position of the operand are 000, the bit in the resulting bit pattern is 000, otherwise 111. The symbol of the bitwise OR operator is pipe (|).

A = 5 = 101 (in binary) 
B = 1 = 001 (in binary) 
A | B = 101 | 001 = 101 = 5 (in decimal)

XOR  

XOR: In bitwise XOR if both bits are the same, the result will be 0, otherwise 1. The symbol of the bitwise XOR operator is caret (^).

A = 5 = 101 (in binary) 
B = 1 = 001 (in binary) 
A ^ B = 101 ^ 001 = 100 = 4 (in decimal)

Left Shift

Left Shift: Left shift operator is a binary operator which shifts bits to the left by a certain number of positions and appends 0 at the right side. One left shift is equivalent to multiplying the bit pattern with 2. The symbol of the left shift operator is <<.

x << y means left shift x by y bits, which is equivalent to multiplying x with $2^y$.

A = 1 = 001 (in binary) 
A << 1 = 001 << 1 = 010 = 2 (in decimal)
A << 2 = 001 << 2 = 100 = 4 (in decimal)

B = 5 = 00101 (in binary)
B << 1 = 00101 << 1 = 01010 = 10 (in decimal)
B << 2 = 00101 << 2 = 10100 = 20 (in decimal)

Right Shift

Right Shift: Right shift operator is a binary operator which shifts bits to the right by a certain number of positions and appends 0 at the left side. One right shift is equivalent to dividing the bit pattern with 2. The symbol of the right shift operator is >>.

x >> y means right shift x by y bits, which is equivalent to dividing x with $2^y$.

A = 4 = 100 (in binary) 
A >> 1 = 100 >> 1 = 010 = 2 (in decimal)
A >> 2 = 100 >> 2 = 001 = 1 (in decimal)
A >> 3 = 100 >> 3 = 000 = 0 (in decimal)

B = 5 = 00101 (in binary)
B >> 1 = 00101 >> 1 = 00010 = 2 (in decimal)

Properties of bitwise operations

Idempotent law

• a & a = a
• a | a = a

Commutative law

• a & b = b & a
• a | b = b | a
• a ^ b = b ^ a

Associativity

• (a & b) & c = a & (b & c)
• (a | b) | c = a | (b | c)
• (a ^ b) ^ c = a ^ (b ^ c)

Distributive law

• (a & b) | c = (a | c) & (b | c)
• (a | b) & c = (a & c) | (b & c)
• (a ^ b) & c = (a & c) ^ (b & c)

De Morgan’s law

• ~ (a & b) = (~a) | (~b)
• ~ (a | b) = (~a) & (~b)

Negative operation properties

• -1 = ~0
• -a = ~(a - 1) Try it in Java, Integer.toBinaryString(int i)

AND properties

• a & 0 = 0
• a & (-1) = a
• a & (~a) = 0

OR properties

• a | 0 = a
• a | (~a) = -1

XOR properties

• a ^ 0 = a
• a ^ a = 0

Other properties

• a & (a-1) is to change the last 1 in binary of a to 0
• a & (-a) equivalent to a & (~(a-1)) is to keep only the last 1 in binary of a, and set the remaining 1s to 0.

Examples

Convert binary to hexadecimal

Now let’s see Convert a Number to Hexadecimal :

Example 1:

Input: num = 26 Output: “1a”

Example 2:

Input: num = -1 Output: “ffffffff”

Method: as it’s from binary to hexadecimal, we could group every 4 digits. With the help of AND operation, we could get last 4 digits via num & 15. Then, right shift the num until it becomes 0. We would use logical right shift therefore high bits are filled with 0. After each group map to 0 ~ f, we get the answer.

class Solution {
    char[] map = {'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
    public String toHex(int num) {
        if (num == 0) return "0";
        StringBuilder res = new StringBuilder();
        // String res = "";
        while (num != 0) {
            res.insert(0,map[(num & 15)]);
            num = (num >>> 4);
        }
        return res.toString();
    }
}

How many 1 bits in this number (Hamming weight)

Number of 1 Bits

Example 1:

Input: n = 00000000000000000000000000001011

Output: 3

Explanation: The input binary string 00000000000000000000000000001011 has a total of three ‘1’ bits.

Method 1: bit mask

Check the $i^{th}$ bit of a number using a bit mask. Start with m = 1, then m <<= 1 making it to 01. After 32 bits checking, we get answer.

public int hammingWeight(int n) {
    int bits = 0;
    int mask = 1;
    for (int i = 0; i < 32; i++) {
        if ((n & mask) != 0) {
            bits++;
        }
        mask <<= 1;
    }
    return bits;
}

Method 2: bit manipulation

Instead of checking every bit of the number, we repeatedly flip the least-significant 1-bit to 0. This is achieved by the property a & (a-1) changing the last 1-bit to 0. As the number becomes 0, we know that it doesn’t have any 1-bit. This method would be a little faster compared to the previous as at worst case, it would check 32 times.

public int hammingWeight(int n) {
    int sum = 0;
    while (n != 0) {
        sum++;
        n &= (n - 1);
    }
    return sum;
}

Reverse Bits

190. Reverse Bits . Reverse bits of a given 32 bits unsigned integer..

This problem could be solved with basic usages of AND and OR operations, as well as shift.

Method:

Start answer with 0, we left shift the answer, right shift the number, checking the last bit is 1 or not, and attach it to answer, with 32 times.

public class Solution {
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res <<= 1;
            res |= (n & 1);
            n >>= 1;
        }
        return res;
    }
}

Sum of Two Integers

Given two integers a and b, return the sum without using the operations + and -. This is to ask: How to perform plus by bit manipulation?

Method:

Think of plus calculation in binary, 0 + 0 = 0, 1 + 0 = 1 in each digit, if there’s 2 one 1 + 1 = 0 and we got a carry 1 to left digit. This is pretty like XOR operation which only got 1 when two digits are different. For carry, we use &, appears only when two digits are 1. Then we left shift the carry to put it at proper digit. In next iteration, we re-perform XOR operation on base number (a) and last left shifted carry, which we assign it to b in previous iteration. When the carry becomes 0, and in XOR we retain each 1 bit in the number, we could return the final answer (a).

Public class Solution {
	public int getSum(int a, int b) {
		while (b != 0) {
			int carry = a & b;
			a = a ^ b;
			b = carry << 1;	
		}	
	}
	return a;
}

 Bitwise AND of Numbers Range

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: left = 5, right = 7

Output: 4

Method:

If any number in the range, has a 0 at a bit ignoring any others, this bit would be 0 after AND. So, as left bound increment, the lower significant bits would be more prone to have 0 and 1, which means we should focus on left side of the binary bits.

Only if all these numbers in range have common prefix bits, then the AND would have 1 in outcome. If right count range over $2^n$, like 16, 32, then the output must be 0.

So how to find the common prefix? We could right shift both bounds, until they were equal and record how many bits we’ve shifted. After the loop we left shift the common prefix the same bits to restore it. That’s the output for range AND.

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shift++;
        }
        return left << shift;
    }
}

Counting Bits

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1’s in the binary representation of i.

Example 1:

Input: n = 2

Output: [0,1,1]

Explanation:

0 –> 0

1 –> 1

2 –> 10

Method:

This can be seen as the follow-up of the Hamming weight problem, counting each number in a loop that repeatedly use a = a & (a - 1) to count least significant bit until a reaches 0. This method might not be efficient. Can we solve it in one-pass $O(n)$ time?

Recall the concept of left shift, or multiply the number by 2, the num of 1 bits remain the same. Then what about the odd number? The odd number will have just 1 more 1-bit than previous even number. Then the problems get solved.

class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n+1];
        res[0] = 0;
        if (n == 0) return res;
        res[1] = 1;
        if (n == 1) return res;
        for (int i = 2; i <= n; i++) {
            if (i % 2 == 0) {
                res[i] = res[i/2];
            } else {
                res[i] = res[i-1] + 1;
            }
			// or we can reduce this logic into one line
			// res[i] = res[i >> 1] + (i & 1);
        }
        return res;
    }
}

Single Number III

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

Example 1:

Input: nums = [1,2,1,3,2,5]

Output: [3,5]

Explanation: [5, 3] is also a valid answer.

Prerequisite:

• a ^ a = 0, any number that appear twice would lead to 0 of XOR
• At any given bit, a ^ a means (a + a) % 2, 1 + 1 = 0, 1 + 0 = 1
• If we were asked to extract numbers that appear three times, we could use (a + a) % 3 at a given bit These are what String Number I and String Number II asked.

For this problem, after all number XOR, we got c = a ^ b (let a and b be the two targets). Then how to extract a and b? Since a ^ b ^ a = b, we could get one given the other. For any two different number, we could locate the rightmost different bit by c & -c which only keep the last 1-bit, since c is derived from a ^ b which means at the 1-bit in c that a and b are different. With this, we could extract a or b, like a mask.

class Solution {
    public int[] singleNumber(int[] nums) {
        // Get the XOR of the final two;
        // c & -c, only keep rightmost 1-bit, to filter a or b;
        int bitmask = 0;
        for (int num: nums) {
            bitmask = bitmask ^ num;
        }
        int diff = bitmask & ~(bitmask - 1);
        int a = 0, b = 0;
        for (int num: nums) {
            if ((num & diff) == 0) {
                a = a ^ num;
            } else {
                b = b ^ num;
            }
        }
        return new int[] {a, b};
    }
}

To be continued

Add more corresponding leetcode problems as examples.