BINARY & BIT OPERATIONS
Complete Study Notes — All Types, Gates, Shifts, Masking & Python Coding
Interview Prep | Competitive Programming | GATE / Placement Exams
1. NUMBER SYSTEMS — FOUNDATIONS
Every number can be represented in different bases (radix). The four systems used in computing:
System Base Digits Used Prefix (Python) Example
Binary 2 0, 1 0b 0b1010 = 10
Octal 8 0–7 0o 0o12 = 10
Decimal 10 0–9 (none) 10
Hexadecimal 16 0–9, A–F 0x 0xA = 10
Conversion Quick Guide
Conversion Method Python One-Liner
Decimal → Binary Divide by 2, collect remainders (bottom-up) bin(42) → '0b101010'
Decimal → Octal Divide by 8, collect remainders oct(42) → '0o52'
Decimal → Hex Divide by 16, collect remainders hex(42) → '0x2a'
Binary → Decimal Multiply each bit × 2^position, sum int('101010',2) → 42
Hex → Binary Each hex digit = 4 bits bin(int('2a',16)) → '0b101010'
Manual Example — 42 in all bases
Decimal 42 = Binary 0b00101010 = Octal 0o52 = Hex 0x2A
Verification: 0×27+0×26+1×25+0×24+1×23+0×22+1×21+0×20 = 32+8+2 = 42 ✓
2. BINARY REPRESENTATION TYPES
2.1 Unsigned Integers
All bits represent magnitude. Range for n bits: 0 to 2n−1
Bits (n) Min Max Total Values
4 0 15 16
8 0 255 256
16 0 65,535 65,536
32 0 4,294,967,295 ~4.3 Billion
64 0 18,446,744,073,709,551,615 ~1.8 × 10<super>19</super>
2.2 Signed Integers — Three Encodings
Sign-Magnitude: MSB = sign bit (0=+ve, 1=−ve), remaining bits = magnitude.
+5 (8-bit) = 00000101 −5 (8-bit) = 10000101
■ Has +0 and −0. Range: −(2n-1−1) to +(2n-1−1)
1's Complement: Invert all bits of the positive number to get negative.
+5 = 00000101 → −5 = 11111010 (flip every bit)
■ Still has +0 (00000000) and −0 (11111111). Range: −(2n-1−1) to +(2n-1−1)
2's Complement (used by ALL modern CPUs): Invert bits then add 1.
+5 = 00000101 Step 1 (invert): 11111010 Step 2 (+1): 11111011 → this is −5
✔ Only one zero. Range: −2n-1 to +(2n-1−1). For 8-bit: −128 to +127
Bits (n) Min (2's comp) Max (2's comp)
8 −128 +127
16 −32,768 +32,767
32 −2,147,483,648 +2,147,483,647
64 −9.2 × 10<super>18</super> +9.2 × 10<super>18</super>
2.3 Floating Point — IEEE 754
Type Total Bits Sign Exponent Mantissa Precision
Single (float) 32 1 8 23 ~7 decimal digits
Double 64 1 11 52 ~15 decimal digits
Half 16 1 5 10 ~3 decimal digits
sign exponent−bias
Formula: value = (−1) × [Link] × 2 (bias = 127 for 32-bit)
3. MSB, LSB, BIT POSITIONS & RANGES
MSB = Most Significant Bit (leftmost, highest value / sign bit in signed). LSB = Least Significant Bit (rightmost,
determines odd/even).
Bit Position 7 (MSB) 6 5 4 3 2 1 0 (LSB)
Bit Weight 128 64 32 16 8 4 2 1
Example: 42 0 0 1 0 1 0 1 0
Key formulas:
Concept Formula / Rule Example (8-bit)
Check bit k n & (1 << k) 42 & (1<<3) → 8 (bit3 is set)
Set bit k n | (1 << k) 42 | (1<<0) → 43
Clear bit k n & ~(1 << k) 42 & ~(1<<1) → 40
Toggle bit k n ^ (1 << k) 42 ^ (1<<2) → 46
LSB value n & 1 42 & 1 → 0 (even)
Lowest set bit n & (-n) 12 & -12 → 4
Clear lowest set bit n & (n-1) 12 & 11 → 8
Count bits in range [l,r] (n >> l) & ((1<<(r-l+1))-1) see masking section
4. LOGIC GATES — ALL TYPES
AND ( & ) — Output 1 only when ALL inputs are 1
A B A AND B
0 0 0
0 1 0
1 0 0
1 1 1
OR ( | ) — Output 1 when ANY input is 1
A B A OR B
0 0 0
0 1 1
1 0 1
1 1 1
NOT ( ~ ) — Inverts input (unary)
A NOT A
0 1
1 0
XOR ( ^ ) — Output 1 when inputs DIFFER
A B A XOR B
0 0 0
0 1 1
1 0 1
1 1 0
NAND ( ~(&) ) — NOT of AND — universal gate
A B A NAND B
0 0 1
0 1 1
1 0 1
1 1 0
NOR ( ~(|) ) — NOT of OR — universal gate
A B A NOR B
0 0 1
0 1 0
1 0 0
1 1 0
XNOR ( ~(^) ) — Output 1 when inputs ARE SAME
A B A XNOR B
0 0 1
0 1 0
1 0 0
1 1 1
Universal Gates Note: NAND and NOR are called universal gates because any Boolean function can be implemented using
only NAND gates (or only NOR gates).
Python Bit-wise Operators Summary
Operator Symbol Python Action on each bit pair
AND & a&b 1 only if both bits = 1
OR | a|b 1 if either bit = 1
XOR ^ a^b 1 if bits DIFFER
NOT ~ ~a Flips all bits (result = −a−1 in Python)
Left Shift << a << n Multiply by 2<super>n</super>, fill 0s from right
Right Shift >> a >> n Divide by 2<super>n</super>, fill sign bit from left
5. SHIFT OPERATIONS — ALL TYPES
5.1 Left Shift ( << )
Shifts all bits LEFT by n positions. Vacated right bits filled with 0. Equivalent to multiplying by 2n (for non-overflow cases).
n = 3 → 0000 0011 n << 2 → 0000 1100 (= 12 = 3 × 4 = 3 × 2²)
5.2 Logical Right Shift ( unsigned >> )
Shifts bits RIGHT, fills vacated left bits with 0. Used for unsigned division by 2n.
n = 12 → 0000 1100 n >> 2 → 0000 0011 (= 3 = 12 ÷ 4)
5.3 Arithmetic Right Shift ( signed >> in Python )
Shifts bits RIGHT, fills vacated left bits with the sign bit (MSB). Preserves the sign for negative numbers.
n = -12 → ...1111 0100 (2's complement) n >> 2 → ...1111 1101 (= -3 = -12 ÷ 4, rounded toward -∞)
In Python, >> is ALWAYS arithmetic (sign-preserving). Python integers have unlimited precision so there is no overflow.
5.4 Circular / Rotate Shift
Bits that fall off one end re-enter from the other end. Python has no built-in rotate operator — implemented manually for
fixed-width:
# Rotate Left n bits in 8-bit width def rotate_left(x, n, bits=8): n %= bits return ((x << n) | (x
>> (bits - n))) & ((1 << bits) - 1) # Rotate Right n bits in 8-bit width def rotate_right(x, n,
bits=8): n %= bits return ((x >> n) | (x << (bits - n))) & ((1 << bits) - 1)
print(rotate_left(0b00110101, 3, 8)) # 0b10101001 = 169 print(rotate_right(0b10110100, 2, 8)) #
0b00101101 = 45
Shift Type Direction Fill Bit Effect Python
Left (<<) ← 0 (right) ×2<super>n</super> x << n
Logical Right (>>) → 0 (left) ÷2<super>n</super> (unsigned) x >> n (for +ve)
Arithmetic Right (>>) → Sign (left) ÷2<super>n</super> (signed) x >> n (any)
Rotate Left ← MSB→LSB Circular manual formula
Rotate Right → LSB→MSB Circular manual formula
6. BIT MASKING — COMPLETE GUIDE
A mask is a bit pattern used with AND/OR/XOR to isolate, set, clear, or toggle specific bits.
6.1 Create Basic Masks
# Mask for bit position k mask = 1 << k # only bit k is 1 # Mask for n-bit number (all 1s) mask =
(1 << n) - 1 # e.g. n=4 → 0b1111 = 15 # Mask for bits [l..r] (inclusive) mask = ((1 << (r - l +
1)) - 1) << l # e.g. bits 2..5 of 8-bit: mask = 0b00111100 = 0x3C
6.2 Core Mask Operations
Operation Code Effect
Read bit k val = (n >> k) & 1 Returns 0 or 1
Set bit k n |= (1 << k) Forces bit k to 1
Clear bit k n &= ~(1 << k) Forces bit k to 0
Toggle bit k n ^= (1 << k) Flips bit k
Extract bits l..r (n >> l) & ((1<<(r-l+1))-1) Returns those bits as integer
Set bits l..r n |= mask_lr Sets range to all 1s
Clear bits l..r n &= ~mask_lr Sets range to all 0s
Copy bit pattern n = (n & ~mask) | (val & mask) Replace bits with val in mask
Check power of 2 n>0 and (n&(n-1))==0 True only for powers of 2
Lowest set bit lsb = n & (-n) Isolates rightmost 1-bit
Remove lowest set n = n & (n-1) Clears rightmost 1-bit
Count 1-bits bin(n).count('1') or n.bit_count() Hamming weight / popcount
6.3 Practical Masking Examples in Python
n = 0b10110110 # = 182 # --- Extract bits 2 to 5 --- mask = ((1 << (5-2+1)) - 1) << 2 # 0b00111100
bits_2_5 = (n & mask) >> 2 # = 0b1101 = 13 # --- Replace bits 2..5 with value 0b0101 --- new_val =
0b0101 n = (n & ~mask) | ((new_val << 2) & mask) # = 0b10010110 # --- Flag / permission system ---
READ = 1 << 0 # 0b001 WRITE = 1 << 1 # 0b010 EXECUTE = 1 << 2 # 0b100 perms = READ | WRITE # 0b011
has_write = bool(perms & WRITE) # True perms &= ~WRITE # revoke write: perms = 0b001
7. BOOLEAN ALGEBRA & DE MORGAN'S LAWS
Law / Identity Expression
Identity A AND 1 = A | A OR 0 = A
Null/Domination A AND 0 = 0 | A OR 1 = 1
Idempotent A AND A = A | A OR A = A
Complement A AND (NOT A) = 0 | A OR (NOT A) = 1
Double Negation NOT(NOT A) = A
Commutative A AND B = B AND A | A OR B = B OR A
Associative (A AND B) AND C = A AND (B AND C)
Distributive A AND(B OR C) = (A AND B) OR (A AND C)
Absorption A AND(A OR B) = A | A OR(A AND B) = A
De Morgan #1 NOT(A AND B) = NOT A OR NOT B → ~(a&b) == (~a)|(~b)
De Morgan #2 NOT(A OR B) = NOT A AND NOT B → ~(a|b) == (~a)&(~b)
Law / Identity Expression
XOR Identity A XOR 0 = A | A XOR A = 0 | A XOR 1 = NOT A
■ De Morgan's Laws are used in compiler optimisations, circuit design, and simplifying conditional logic in code.
8. PYTHON BIT OPERATIONS — FULL REFERENCE
Python integers are arbitrary precision — no overflow, no unsigned type. The ~ operator returns −n−1 (because Python
uses 2's complement with infinite width).
# Basic operators a, b = 60, 13 # 60=0b111100 13=0b001101 print(a & b) # 12 → 0b001100 (AND)
print(a | b) # 61 → 0b111101 (OR) print(a ^ b) # 49 → 0b110001 (XOR) print(~a) # -61 → -(60+1)
(NOT) print(a << 2) # 240 → 0b11110000 (left shift ×4) print(a >> 2) # 15 → 0b001111 (right shift
÷4) # Useful built-ins print(bin(a)) # '0b111100' print(a.bit_length()) # 6 (min bits needed)
print(a.bit_count()) # 4 (popcount, Python 3.10+) print(bin(a).count('1')) # 4 (popcount, older
Python)
Format functions
n = 42 print(f'{n:b}') # '101010' plain binary print(f'{n:08b}') # '00101010' zero-padded 8 bits
print(f'{n:#010b}') # '0b00101010' with 0b prefix, 10 chars print(f'{n:x}') # '2a' hex
print(f'{n:08x}') # '0000002a' zero-padded hex print(f'{n:o}') # '52' octal
9. TOP CODING QUESTIONS — BIT MANIPULATION
Q1. Count number of 1-bits (Hamming Weight / Popcount)
def count_ones(n): count = 0 while n: n &= n - 1 # clear the lowest set bit each time count += 1
return count # count_ones(29) = count_ones(0b11101) = 4 # Python 3.10+: n.bit_count() gives same
result
■ Brian Kernighan's algorithm — O(number of 1-bits). Each step removes one 1-bit via n & (n-1).
Q2. Check if a number is a power of 2
def is_power_of_2(n): return n > 0 and (n & (n - 1)) == 0 # Powers of 2 have exactly one 1-bit. #
n-1 flips all bits below and including that bit. # So n & (n-1) == 0 iff only one bit is set.
■ Works in O(1). Remember: 0 is NOT a power of 2.
Q3. Find the only non-repeated element (XOR trick)
def single_number(nums): result = 0 for x in nums: result ^= x # identical pairs cancel to 0
return result # single_number([4,1,2,1,2]) = 4 # XOR properties: a^a=0, a^0=a, XOR is
commutative+associative
■ Classic LeetCode Q136. O(n) time, O(1) space.
Q4. Reverse bits of a 32-bit integer
def reverse_bits(n): result = 0 for _ in range(32): result = (result << 1) | (n & 1) n >>= 1
return result # Extract LSB of n, push into MSB of result, repeat 32 times.
■ LeetCode Q190. Extract bit-by-bit from right, build from left.
Q5. Find two non-repeated elements in array
def two_singles(nums): xor = 0 for x in nums: xor ^= x # xor = a ^ b diff_bit = xor & (-xor) #
rightmost differing bit a = b = 0 for x in nums: if x & diff_bit: a ^= x # group 1 else: b ^= x #
group 2 return a, b
■ Split elements into 2 groups by a differing bit. XOR within each group gives result.
Q6. Check if two integers have opposite signs
def opposite_signs(a, b): return (a ^ b) < 0 # XOR of two numbers with opposite signs has MSB = 1
# (negative in Python's signed interpretation)
■ O(1). MSB (sign bit) is 1 when signs differ.
Q7. Swap two numbers without temp variable
a, b = 5, 9 a ^= b # a = a XOR b b ^= a # b = b XOR (a XOR b) = a (original) a ^= b # a = (a XOR b)
XOR a = b (original) # Result: a=9, b=5 — no extra memory used
■ XOR swap. Works because XOR is its own inverse.
Q8. Count bits to flip to convert A to B
def bits_to_flip(a, b): xor = a ^ b # 1-bits mark positions that differ count = 0 while xor: xor
&= xor - 1 # remove lowest 1-bit count += 1 return count # bits_to_flip(29, 15) =
bits_to_flip(0b11101, 0b01111) = 2
■ XOR gives a 1 wherever bits differ; then count those 1-bits.
Q9. Find position of rightmost set bit
def rightmost_set_bit(n): if n == 0: return -1 pos = 0 while not (n & 1): n >>= 1 pos += 1 return
pos # OR compact: import math; math.log2(n & -n) (if n != 0)
■ n & (-n) isolates the rightmost set bit; log2 gives position.
Q10. Generate all subsets (power set) using bitmask
def power_set(arr): n = len(arr) result = [] for mask in range(1 << n): # 0 to 2^n - 1 subset =
[arr[i] for i in range(n) if mask & (1 << i)] [Link](subset) return result #
power_set([1,2,3]) → 8 subsets including []
■ Each bit in mask decides whether element i is in the subset. O(n × 2^n).
Q11. Multiply by 7 without * operator
def mul7(n): return (n << 3) - n # 8n - n = 7n # Similarly: multiply by 3 = (n<<1)+n, by 6 =
(n<<2)+(n<<1)
■ Use shifts for powers of 2 and combine: 7 = 8-1 = 2³-1.
Q12. Next Power of 2 (ceiling)
def next_power_of_2(n): if n <= 0: return 1 n -= 1 n |= n >> 1 n |= n >> 2 n |= n >> 4 n |= n >> 8
n |= n >> 16 return n + 1 # next_power_of_2(6) = 8, next_power_of_2(8) = 8
■ OR-spreading fills all lower bits with 1, then +1 gives next power.
10. QUICK REFERENCE CHEAT SHEET
Operation Expression Result (n=12=0b1100)
AND n & 10 12&10=8 (0b1000)
OR n|3 12|3=15 (0b1111)
XOR n ^ 10 12^10=6 (0b0110)
NOT ~n ~12 = -13
Left shift ×2 n << 1 24
Left shift ×8 n << 3 96
Right shift ÷4 n >> 2 3
Check odd n&1 0 (even)
Set bit 1 n | (1<<1) 14
Clear bit 3 n & ~(1<<3) 4
Toggle bit 2 n ^ (1<<2) 8
Lowest set bit n & (-n) 4
Remove lowest set bit n & (n-1) 8
Is power of 2? n>0 and (n&(n-1))==0 False (12 not power of 2)
Bit length n.bit_length() 4
Popcount bin(n).count('1') 2
Mask 4-bit lower nibble n & 0xF 12
Mask upper nibble (n >> 4) & 0xF 0
Next power of 2 use function above 16
Negative Numbers in Python — Important !
Python integers have infinite precision, so negative numbers in Python behave like two's complement with infinite sign
extension. For fixed-width operations (e.g. 32-bit), always mask with (1 << 32) - 1 to prevent unexpected results:
n = -1 print(bin(n)) # '-0b1' — Python shows sign separately # Force into 8-bit unsigned
representation: n8 = n & 0xFF # 255 = 0b11111111 print(f'{n8:08b}') # '11111111' # Force into
32-bit: n32 = n & 0xFFFFFFFF # 4294967295
11. TRICKY INTERVIEW TIPS & PATTERNS
Pattern / Trick Key Insight
XOR Cancellation a ^ a = 0 and a ^ 0 = a — pairs cancel. Use to find unique elements, check duplicates, swap values.
n & (n-1) trick Clears the lowest set bit. Loop count = number of 1-bits (Brian Kernighan). Also: n & (n-1) == 0 means power of 2.
n & (-n) trick Isolates the lowest set bit. Used in Fenwick Trees / BIT for index navigation.
XOR for parity XOR all elements: result is 0 if even number of 1-bits total, else 1. Parity check.
Shift vs Multiply Prefer shifts: x<<1 is faster than x*2. Use (x<<3)-(x) = 7x for multiply by 7.
Mask extraction Always right-shift after AND to get the numeric value: val = (n >> l) & mask
Sign bit check For 32-bit: MSB set → (n & (1<<31)) != 0. In Python: n < 0 for signed, mask for unsigned.
Avoid ~ on unsigned ~n in Python gives -(n+1). For unsigned NOT on n bits: (n ^ ((1<<bits)-1))
Pattern / Trick Key Insight
Bit DP subsets To iterate over all subsets of a bitmask m: for sub in range(m, 0, -1): sub &= m — classic competitive trick.
Gray Code Binary to Gray: g = n ^ (n >> 1). Gray to Binary: b = g; b ^= b>>1; b ^= b>>2; ...
Binary & Bit Operations — Complete Notes | Python 3.x | For GATE / Placement / Competitive Programming