Bit Manipulation

Bit Manipulation by Hand:

^ means XOR, ~ is a Not (Negation)

- XOR: If it's a different bit, it will be 1.

 

EX) 1101 ^ (~1101) = 1111

- If you XOR a bit with its own negated value, you will always get 1. Therefore, the solution to a^(~a) will be a sequence of 1s.

EX) 1011 & (~0 << 2) = 1000

~0 is a sequence of 1s, so ~0 << 2 is 1s followed by two 0s. ANDing that with another value will clear the last two bits of the value. 

 

Bit Facts and Tricks:

The following expressions are useful in bit manipulations. Don't just memorize them, though; think deeply about why each of these is true. We use "1s" and "0x" to indicate a sequence of 1s or 0s, respectively.

 

x ^ 0s = x

x & 0s = 0

x | 0s = x

x ^ 1s = ~x

x & 1s = x

x | 1s = 1s

x ^ x = 0

x & x = x

x | x = x

 

Two's complement and Negative Numbers

Computers typically store integers in two's complement representation. A positive number is represented as itself while a negative number is represented as the two's complement of its absolute value (with a 1 in its sign bit to indicate that a negative value). The two's complement of an N-bit number (where N is the number of bits used for the number, excluding the sign bit) is the complement of the number with respect to 2^n.

 

In 4 bit representation:

7 = 0111

6 = 0110

5 = 0101

4 = 0100

3 = 0011

2 = 0010

1 = 0001

0 = 0000

-1 = 1111

-2 = 1110

-3 = 1101

-4 = 1100

-5 = 1011

-6 = 1010

-7 = 1001

 

Arithmetic vs. Logical Right Shift

The arithmetic right shift essentially divides by 2.

The logical right shift does what we would visually see as shifting the bits.

 

In a logical right shift, we shift the bits and put a 0 in the most significant bit. It it indicated with a >>> operator. On an 8-bit integer (where the sign bit is the most significant bit), this would look like the image below. 

 

10110101 = -75

01011010 = 90

 

In an arithmetic right shift, we shift values to the right but fill in the new bits with the value of the sign bit. This has the effect of dividing by two. It is indicated by a >> operator.

 

10110101 = -75

11011010 = -38

 

Common Bit Tasks: Geting and Setting

 

Get Bit

This method shifts 1 over by i bits, creating a value that looks like 00010000. By performing an AND with num, we clear all bits other than the bit at the bit i. Finally, we compare that to 0. If that new value is not zero then bit I must have a 1. Otherwise, bit i is a 0.

boolean getBit(int num, int i){
	return ((num & (1 << i)) != 0);
}

 

Set Bit

SetBit shifts 1 over by i bits, creating a value like 00010000. By performing an OR with num, only the value at bit i will change. All other bits of the mask are zero and will not affect num.

int setBit(int num, int i) {
	return num | (1 << i);
}

 

Clear Bit

This method operates in almost the reverse of setBit. First, we create a number like 11101111 by creating the reverse of it (00010000) and negating it. THen, we perform an AND with num. This will clear the ith bit and leave the remainder unchanged.

int clearBit(int num, int i) {
	int mask = ~(1 << i);
    return num & mask;
}

To clear all bit from the most significant bit through i (inclusive), we create a mask with a 1 at the ith bit (1 << i). Then, we subtract 1 from it, giving us a sequence of 0s followed by i 1s. We then AND our number with this mask to leave just the last i bits. 

int clearBitsMSBthroughI(int num, int i) {
	int mask = (1 << i) - 1;
    return num & mask;
}

To clear all bits from i through 0 (inclusive), we take a sequence of all 1s (which is -1) and shift it left by i + 1 bits. This gives us a sequence of 1s ( in the most significant bits) followed by i 0 bits.

int clearBitsIthrough0(int num, int i) {
	int mask = (-1 << (i + 1));
    return num & mask;
}

 

Update Bit

To set the ith bit to a value v, we first clear the bit at position i by using a mask that looks like 11101111. Then, we shift the intended value, v, left by i bits. This will create a number with bit i equal to v and all other bits equal to 0. Finally, we OR these two numbers, updating the ith bit if v is 1 and leaving it as 0 otherwise.

int updateBit(int num, int i, boolean bitIs1) {
	int value = bitIs1 ? 1: 0;
    int mask = ~(1 << i);
    return (num & mask) | (value << i);
}