Bits Manipulation

Question 1

For integer x, how to single out / isolate / get its last bit?

Answer 1

x & 1

current digit & current bit for bit mask
0 & 1 = 0
1 & 1 = 1

0 & 0 = 0
1 & 0 = 0
& 1 doesn’t change the value of the bit.
& 0 turns a bit to 0

Question 2

What does x & 1 do for value x?

0 & 1 = 0
1 & 1 = 1

0 & 0 = 0
1 & 0 = 0

Answer 2

It singles out / isolates / gets the last bit of integer x.

& 1 doesn’t change the value of the bit.
& 0 turns a bit to 0

Question 3

What is a set bit?
What is a cleared / unset bit?

Answer 3

1
Set Bit Definition: A set bit is a bit with a value of 1 in a binary representation. The term “set” indicates the bit is “on.”

0 is called a cleared bit or an unset bit. A cleared/unset bit indicates that the position is “off” or inactive.

Question 4

What is the lowest set bit?

Answer 4

the right most 1 of a binary number

Set Bit Definition: A set bit is a bit with a value of 1 in a binary representation. The term “set” indicates the bit is “on.”

Question 5

How to drop the lowest set bit (the rightmost 1) in the binary representation of x?

AND is often used to drop / isolate values

Answer 5

Bitwise AND Operation (x &= x - 1)
x = 10100
x - 1 = 10011
x & (x - 1) = 10000
As you can see, the result 10000 is x with the lowest set bit removed.

1. This works because the rightmost 1 is followed by 0 (or is the last bit).
2. If we subtract 1 from x, It flips all the digits to the right hand of the last 1 to 0, whereas the last 1 flips to 0.
3. but all the digits on the left hand of the last bit 1 remains the same.
4. when we x & (x - 1) it turns the last 1 to 0 while keeping all digits at its right hand 0

Question 6

What does x &= x - 1 do to the binary representation of x?

Why does it work?

AND is often used to drop / isolate values

Answer 6

It drops the lowest set bit (the rightmost 1) in the binary representation of x.

Bitwise AND Operation (x &= x - 1)
x = 10100
x - 1 = 10011
x & (x - 1) = 10000
As you can see, the result 10000 is x with the lowest set bit removed.

1. This works because the rightmost 1 is followed by 0 (or is the last bit).
2. If we subtract 1 from x, It flips all the digits to the right hand of the last 1 to 0, whereas the last 1 flips to 0.
3. but all the digits on the left hand of the last bit 1 remains the same.
4. when we x & (x - 1) it turns the last 1 to 0 while keeping all digits at its right hand 0

Question 7

the parity of a binary word is
1 when there are odd number of 1s in the binary representation
0 when there are even number of 1s in the binary representation

def parity(int: x) -> int:
cnt = 0
while x:
cnt ^= x & 1
x&raquo_space;= 1
return cnt

Why does this work?
XOR is often used for flipping or swapping values

Answer 7

x & 1 singles out the last digit of a binary representation

cnt only flips when it encounters a digit 1

cnt ^ (x&1) = newCnt
1 ^ 1 = 0 (flip)
0 ^ 1 = 1 (flip)
1 ^ 0 = 1 (no flip)
0 ^ 0 = 0 (no flip)

when a = a ^ b
a only flips when b = 1
a stays the same when b = 0

Question 8

int a = 5, b = 3;
a ^= b;
b ^= a;
a ^= b;
// Now a = 3, b = 5

Answer 8

XOR is often used for flipping or swapping values

Question 9

Using bitwise operation, how to swap the value of
int a = 5, b = 3;
to become
a = 3, b = 5

XOR is often used for flipping or swapping values

Answer 9

int a = 5, b = 3;
a ^= b;
b ^= a;
a ^= b;
// Now a = 3, b = 5

Question 10

How to remove the lowest set bit in x?

How to extract the lowest set bit in x?

Answer 10

How to remove the lowest set bit in x?

x & (x - 1)

How to extract the lowest set bit in x?

x & ~(x - 1)