DSA Bits and Bitwise Operations
Bitwise operations act on a number one binary digit at a time. A binary digit is called a bit, and it holds only 0 or 1.
AND and OR, bit by bit
AND compares each pair of bits in the same position. OR compares the same pairs with its own rule.
a = 12
b = 10
print("a:", a, format(a, "08b"))
print("b:", b, format(b, "08b"))
print("a AND b:", a & b, format(a & b, "08b"))
print("a OR b:", a | b, format(a | b, "08b"))XOR, bit by bit
XOR keeps a position when the two bits differ. Equal bits give 0 in that position.
a = 12
b = 10
print("a XOR b:", a ^ b, format(a ^ b, "08b"))
print("a XOR a:", a ^ a, format(a ^ a, "08b"))Shifts move every bit
A left shift by one doubles a whole number. A right shift by one halves a whole number, dropping any remainder.
n = 5
print("start:", n, format(n, "08b"))
print("left 1:", n << 1, format(n << 1, "08b"))
print("left 2:", n << 2, format(n << 2, "08b"))
print("20 right 2:", 20 >> 2, format(20 >> 2, "08b"))A bitmask selects bits
A mask with a single 1 tests one chosen position. The result is nonzero only when that bit is set.
flags = 0b1010
for pos in range(4):
mask = 1 << pos
print("position", pos, "set:", (flags & mask) != 0)Example
a = 0b10110100
b = 0b01101010
print("a:", a, format(a, "08b"))
print("b:", b, format(b, "08b"))
print("AND:", a & b, format(a & b, "08b"))
print("OR:", a | b, format(a | b, "08b"))
print("XOR:", a ^ b, format(a ^ b, "08b"))
print("a left 1:", a << 1, format(a << 1, "09b"))
print("a right 2:", a >> 2, format(a >> 2, "08b"))Key points
- Bitwise operations act on a number one binary digit at a time.
- AND keeps a bit only when both input bits are 1.
- OR keeps a bit when at least one input bit is 1.
- XOR keeps a bit when exactly one input bit is 1.
- A left shift moves every bit one place toward the higher end.
- A right shift moves every bit one place toward the lower end.
- A bitmask is a pattern of bits used to select chosen bits.
In this example, the two bytes are printed in binary first. AND keeps only the positions where both bytes hold 1. OR keeps every position where either byte holds 1. XOR keeps the positions where the bytes differ. The last two lines shift the first byte left and then right.
Note
Python integers have no fixed width, so a mask sets the working width.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
What does 0b1100 AND 0b1010 give?