Bitwise Operators - Learning Module

Loading content...

0/276

Truth Tables and Examples

Bringing It All Together

Having explored AND, OR, XOR, and NOT individually, it's time to see them working together. Real-world bit manipulation rarely uses a single operator in isolation—practical solutions combine operators in patterns that leverage each one's strengths.

This page serves as both a reference and a synthesis. We'll present complete truth tables for quick lookup, explore how operators combine, understand precedence rules, and walk through comprehensive examples that demonstrate professional-grade bit manipulation techniques.

What You Will Learn

By the end of this page, you will have a comprehensive reference for all bitwise operators, understand operator precedence to avoid bugs, see how operators combine for complex bit manipulation, and internalize the complete mental model for thinking at the bit level.

Complete Truth Table Reference

Here are all bitwise operators in a single comprehensive reference. These truth tables should become second nature—memorize them!

Binary Operators (Two Operands):

Complete Binary Operator Truth Tables
A	B	A AND B	A OR B	A XOR B
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

Unary Operator (One Operand):

NOT Operator Truth Table
A	NOT A
0	1
1	0

Memory Aids for Each Operator:

Operator	Symbol	Memory Aid	Output 1 When...
AND	`&`	Both must agree (1 AND 1)	Both inputs are 1
OR	`\|`	Either is enough	At least one input is 1
XOR	`^`	Must be different	Exactly one input is 1
NOT	`~`	Flip everything	(Unary) Input is 0

Counting Outputs

Notice the output patterns: AND outputs 1 once (25%), OR outputs 1 three times (75%), XOR outputs 1 twice (50%). These percentages affect the expected density of 1s after operations—useful for reasoning about probabilistic behavior in hashing and encryption.

Derived Operations — NAND, NOR, XNOR

By combining NOT with the binary operators, we get three derived operations that are important in hardware design and occasionally useful in software.

Derived Operator Truth Tables
A	B	NAND (NOT AND)	NOR (NOT OR)	XNOR (NOT XOR)
0	0	1	1	1
0	1	1	0	0
1	0	1	0	0
1	1	0	0	1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// NAND: NOT(A AND B) — outputs 0 only when both are 1
function nand(a: number, b: number): number {
    return ~(a & b);
}
 
// NOR: NOT(A OR B) — outputs 1 only when both are 0
function nor(a: number, b: number): number {
    return ~(a | b);
}
 
// XNOR: NOT(A XOR B) — outputs 1 when inputs are same
// Also called equivalence or biconditional
function xnor(a: number, b: number): number {
    return ~(a ^ b);
}
 
// Single-bit examples
console.log(nand(1, 1) & 1);  // 0 (NOT(1 AND 1) = NOT 1 = 0)
console.log(nor(0, 0) & 1);   // 1 (NOT(0 OR 0) = NOT 0 = 1)
console.log(xnor(1, 1) & 1);  // 1 (NOT(1 XOR 1) = NOT 0 = 1)
console.log(xnor(1, 0) & 1);  // 0 (NOT(1 XOR 0) = NOT 1 = 0)
 
// XNOR for equality detection (per bit)
// If bits are equal, result bit is 1
const val1 = 0b10110011;
const val2 = 0b10110011;
console.log((~(val1 ^ val2) >>> 0).toString(2));
// All 1s if values are equal!

NAND and NOR are Universal

Any Boolean function can be built using only NAND gates (or only NOR gates). This makes them foundational in chip design. While less common in everyday programming, understanding them helps with hardware interfacing and Boolean expression simplification.

Operator Precedence

One of the most common sources of bugs in bit manipulation is operator precedence. Bitwise operators have lower precedence than comparison operators in most languages, which leads to surprising behavior.

Typical Precedence (highest to lowest):

~ (NOT) — unary, highest
* / % — multiplication, division
+ - — addition, subtraction
<< >> >>> — shift operators
< <= > >= — comparisons
== != === !== — equality
& — AND
^ — XOR
| — OR
&& — logical AND
|| — logical OR

The Precedence Trap

Bitwise operators have LOWER precedence than comparison operators! This means x & 1 == 0 is parsed as x & (1 == 0) → x & false → x & 0 → always 0! You almost always want (x & 1) == 0. Always use parentheses with bitwise operators.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// BUG: Check if bit 0 is set
const x = 5;  // 0b101
 
// WRONG: This checks (1 == 0) first, which is false (0)
// Then: x & 0 = 0, which is falsy
if (x & 1 == 0) {
    console.log("BUG: This always executes!");
}
 
// RIGHT: Parenthesize the bitwise operation
if ((x & 1) == 0) {
    console.log("Bit 0 is NOT set");  // Won't execute for x=5
} else {
    console.log("Bit 0 IS set");  // This executes
}
 
// BUG: Testing multiple flags
const flags = 0b1010;
const FLAG_A = 0b0010;
const FLAG_B = 0b1000;
 
// WRONG: | has lower precedence than !=
if (flags & FLAG_A | FLAG_B != 0) {  // Parsed as: flags & (FLAG_A | (FLAG_B != 0))
    console.log("Confusing behavior!");
}
 
// RIGHT: Explicit parentheses
if ((flags & (FLAG_A | FLAG_B)) != 0) {
    console.log("Has FLAG_A or FLAG_B or both");
}
 
// SAFEST: Compare the complete expression
if ((flags & FLAG_A) !== 0 || (flags & FLAG_B) !== 0) {
    console.log("Has FLAG_A or FLAG_B or both");  // Crystal clear
}

Golden Rule: When in doubt, add parentheses. The performance cost is zero (it affects only parsing), and the clarity gain is immense.

Combined Operator Patterns

The real power of bitwise operations emerges when operators are combined into patterns. Here are the most important compound operations.

Essential Bit Manipulation Patterns
Operation	Expression	Description
Check bit n	`(x & (1 << n)) !== 0`	Test if bit n is set
Set bit n	`x \| (1 << n)`	Turn bit n on
Clear bit n	`x & ~(1 << n)`	Turn bit n off
Toggle bit n	`x ^ (1 << n)`	Flip bit n
Extract bit n	`(x >> n) & 1`	Get bit n as 0 or 1
Clear lowest set bit	`x & (x - 1)`	Turn off rightmost 1
Isolate lowest set bit	`x & (-x)`	Keep only rightmost 1
Set lowest clear bit	`x \| (x + 1)`	Turn on rightmost 0
Check power of 2	`x && !(x & (x-1))`	True if exactly one bit set
Count trailing zeros	(see code)	Position of lowest set bit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// Comprehensive bit manipulation utility class
class BitOps {
    // Check if bit at position n is set
    static isSet(x: number, n: number): boolean {
        return (x & (1 << n)) !== 0;
    }
    
    // Set bit at position n to 1
    static set(x: number, n: number): number {
        return x | (1 << n);
    }
    
    // Clear bit at position n to 0
    static clear(x: number, n: number): number {
        return x & ~(1 << n);
    }
    
    // Toggle bit at position n
    static toggle(x: number, n: number): number {
        return x ^ (1 << n);
    }
    
    // Extract bit at position n as 0 or 1
    static extract(x: number, n: number): number {
        return (x >> n) & 1;
    }
    
    // Update bit n to a specific value (0 or 1)
    static update(x: number, n: number, value: 0 | 1): number {
        // Clear the bit, then OR with the new value
        return (x & ~(1 << n)) | (value << n);
    }
    
    // Extract bits from start to end (inclusive)
    static extractRange(x: number, start: number, end: number): number {
        const width = end - start + 1;
        const mask = (1 << width) - 1;
        return (x >> start) & mask;
    }
}
 
// Demo
let flags = 0b10100101;
console.log("Initial:", flags.toString(2).padStart(8, '0'));  // 10100101
 
console.log("Bit 2 set?", BitOps.isSet(flags, 2));  // true
console.log("Bit 3 set?", BitOps.isSet(flags, 3));  // false
 
flags = BitOps.set(flags, 3);
console.log("After set(3):", flags.toString(2).padStart(8, '0'));  // 10101101
 
flags = BitOps.clear(flags, 0);
console.log("After clear(0):", flags.toString(2).padStart(8, '0')); // 10101100
 
flags = BitOps.toggle(flags, 7);
console.log("After toggle(7):", flags.toString(2).padStart(8, '0')); // 00101100
 
console.log("Extract bits 2-4:", BitOps.extractRange(0b11011010, 2, 4).toString(2)); // "110"

The Update Pattern

To set a bit to a specific value (not just 1 or 0), use the clear-then-set pattern: (x & ~(1 << n)) | (value << n). First clear the bit with AND-NOT, then set it with OR. This works for single bits and can be extended to multi-bit fields.

Complete Worked Example — Bit Field Manipulation

Let's work through a comprehensive example that uses all operators together: parsing and manipulating a packed data structure representing a game entity's state.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/**
 * Entity State Bit Layout (32 bits total):
 * 
 * Bits 0-9:   Health (0-1023)
 * Bits 10-14: Level (0-31)
 * Bits 15-19: Armor (0-31)
 * Bits 20-23: Weapon ID (0-15)
 * Bits 24-27: Status Flags (4 individual flags)
 * Bits 28-31: Reserved (unused)
 */
 
class EntityState {
    private state: number = 0;
    
    // Bit positions and widths
    private static readonly HEALTH_START = 0;
    private static readonly HEALTH_WIDTH = 10;
    private static readonly LEVEL_START = 10;
    private static readonly LEVEL_WIDTH = 5;
    private static readonly ARMOR_START = 15;
    private static readonly ARMOR_WIDTH = 5;
    private static readonly WEAPON_START = 20;
    private static readonly WEAPON_WIDTH = 4;
    private static readonly FLAGS_START = 24;
    
    // Status flags
    static readonly FLAG_POISONED = 1 << 24;
    static readonly FLAG_STUNNED = 1 << 25;
    static readonly FLAG_INVINCIBLE = 1 << 26;
    static readonly FLAG_INVISIBLE = 1 << 27;
    
    // Extract a field using shift and mask
    private extractField(start: number, width: number): number {
        const mask = (1 << width) - 1;  // Create width-bit mask
        return (this.state >> start) & mask;  // Shift and mask
    }
    
    // Update a field using clear-then-set
    private updateField(start: number, width: number, value: number): void {
        const mask = (1 << width) - 1;        // Width-bit mask
        const fieldMask = mask << start;      // Mask in position
        
        // Clear field with AND ~mask, then set with OR
        this.state = (this.state & ~fieldMask) | ((value & mask) << start);
    }
    
    // --- Getters ---
    get health(): number {
        return this.extractField(EntityState.HEALTH_START, EntityState.HEALTH_WIDTH);
    }
    
    get level(): number {
        return this.extractField(EntityState.LEVEL_START, EntityState.LEVEL_WIDTH);
    }
    
    get armor(): number {
        return this.extractField(EntityState.ARMOR_START, EntityState.ARMOR_WIDTH);
    }
    
    get weaponId(): number {
        return this.extractField(EntityState.WEAPON_START, EntityState.WEAPON_WIDTH);
    }
    
    // --- Setters ---
    set health(value: number) {
        this.updateField(EntityState.HEALTH_START, EntityState.HEALTH_WIDTH, value);
    }
    
    set level(value: number) {
        this.updateField(EntityState.LEVEL_START, EntityState.LEVEL_WIDTH, value);
    }
    
    set armor(value: number) {
        this.updateField(EntityState.ARMOR_START, EntityState.ARMOR_WIDTH, value);
    }
    
    set weaponId(value: number) {
        this.updateField(EntityState.WEAPON_START, EntityState.WEAPON_WIDTH, value);
    }
    
    // --- Flag operations ---
    hasFlag(flag: number): boolean {
        return (this.state & flag) !== 0;  // AND to check
    }
    
    setFlag(flag: number): void {
        this.state |= flag;  // OR to set
    }
    
    clearFlag(flag: number): void {
        this.state &= ~flag;  // AND NOT to clear
    }
    
    toggleFlag(flag: number): void {
        this.state ^= flag;  // XOR to toggle
    }
    
    // --- Raw state access ---
    getRawState(): number { return this.state; }
    setRawState(state: number): void { this.state = state; }
    
    toString(): string {
        return `Health:${this.health} Level:${this.level} Armor:${this.armor} ` +
               `Weapon:${this.weaponId} Flags:[${this.getFlagsString()}]`;
    }
    
    private getFlagsString(): string {
        const flags: string[] = [];
        if (this.hasFlag(EntityState.FLAG_POISONED)) flags.push("POISONED");
        if (this.hasFlag(EntityState.FLAG_STUNNED)) flags.push("STUNNED");
        if (this.hasFlag(EntityState.FLAG_INVINCIBLE)) flags.push("INVINCIBLE");
        if (this.hasFlag(EntityState.FLAG_INVISIBLE)) flags.push("INVISIBLE");
        return flags.join(", ");
    }
}
 
// Demo usage
const entity = new EntityState();
entity.health = 750;
entity.level = 25;
entity.armor = 18;
entity.weaponId = 7;
entity.setFlag(EntityState.FLAG_POISONED);
entity.setFlag(EntityState.FLAG_INVISIBLE);
 
console.log(entity.toString());
// Health:750 Level:25 Armor:18 Weapon:7 Flags:[POISONED, INVISIBLE]
 
console.log("Raw state:", (entity.getRawState() >>> 0).toString(2).padStart(32, '0'));
// Shows the actual bit pattern!

Performance Comparison with Alternatives

Bitwise operations are fast—often the fastest operations a CPU can perform. But how much faster are they compared to alternatives?

Operation Performance Comparison (Approximate CPU Cycles)
Operation Type	Example	Typical Cycles	Notes
Bitwise AND/OR/XOR/NOT	`a & b`	1	Fastest possible
Bit Shift	`a << 3`	1	Equally fast
Integer Add/Subtract	`a + b`	1	Same as bitwise
Integer Multiply	`a * b`	3-4	Slightly slower
Integer Divide	`a / b`	20-40	Much slower
Modulo	`a % b`	20-40	Same as divide
Floating Point Op	`a * 1.5`	3-6	Modern CPUs are fast
Branch/Conditional	`if (x)`	1-15+	Depends on prediction
Memory Access (L1)	`arr[i]`	3-4	Cache hit
Memory Access (RAM)	`arr[i]`	100-300	Cache miss

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Multiply by 2: Bitwise is faster (but compilers often optimize)
const mulBy2Arithmetic = (n: number) => n * 2;
const mulBy2Bitwise = (n: number) => n << 1;
 
// Divide by power of 2: Bitwise is much faster
const divBy8Arithmetic = (n: number) => Math.floor(n / 8);
const divBy8Bitwise = (n: number) => n >> 3;  // For positive numbers
 
// Modulo by power of 2: Bitwise is dramatically faster
const mod16Arithmetic = (n: number) => n % 16;
const mod16Bitwise = (n: number) => n & 15;  // 16-1 = 15 = 0b1111
 
// Check even/odd
const isEvenArithmetic = (n: number) => n % 2 === 0;
const isEvenBitwise = (n: number) => (n & 1) === 0;
 
// Swap (no temp variable)
function swapArithmetic(a: number, b: number): [number, number] {
    const temp = a; a = b; b = temp;
    return [a, b];
}
function swapBitwise(a: number, b: number): [number, number] {
    a ^= b; b ^= a; a ^= b;
    return [a, b];
}
 
// Note: For readability and correctness, prefer obvious code unless
// you've profiled and confirmed the operation is a bottleneck.
// Modern compilers often optimize arithmetic to bitwise anyway!

When to Optimize

Modern compilers are remarkably good at optimizing common patterns. n * 2 becomes n << 1, n % 8 becomes n & 7, etc. Use bitwise explicitly when: (1) clarity is maintained, (2) the compiler might not recognize the pattern, or (3) you're writing performance-critical inner loops you've actually profiled.

Common Bit Manipulation Interview Patterns

Bit manipulation appears frequently in technical interviews. Here are patterns that appear repeatedly, using combinations of all operators.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// Count the number of 1 bits in an integer
 
// Method 1: Simple loop (O(bits))
function countBitsSimple(n: number): number {
    let count = 0;
    while (n !== 0) {
        count += n & 1;  // Add lowest bit
        n >>>= 1;        // Shift right (unsigned)
    }
    return count;
}
 
// Method 2: Brian Kernighan's Algorithm (O(set bits))
// Each iteration clears the lowest set bit
function countBitsKernighan(n: number): number {
    let count = 0;
    while (n !== 0) {
        n = n & (n - 1);  // Clear lowest set bit
        count++;
    }
    return count;
}
 
// Method 3: Parallel bit counting (O(1) operations)
// Uses clever bit manipulation to count in parallel
function countBitsParallel(n: number): number {
    n = n - ((n >>> 1) & 0x55555555);           // Count pairs
    n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);  // Count nibbles
    n = (n + (n >>> 4)) & 0x0F0F0F0F;          // Count bytes
    n = n + (n >>> 8);                          // Count 16-bit halves
    n = n + (n >>> 16);                         // Count 32-bit total
    return n & 0x3F;                            // Mask to 6 bits (max 32)
}
 
console.log(countBitsSimple(0b10110101));     // 5
console.log(countBitsKernighan(0b10110101));  // 5
console.log(countBitsParallel(0b10110101));   // 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Check if a number is a power of 2
// Powers of 2 have exactly one bit set
 
function isPowerOfTwo(n: number): boolean {
    // n must be positive, and n & (n-1) must be 0
    return n > 0 && (n & (n - 1)) === 0;
}
 
// Why it works:
// n = 8 = 0b1000
// n-1 = 7 = 0b0111
// n & (n-1) = 0b0000 → is power of 2!
 
// n = 6 = 0b0110
// n-1 = 5 = 0b0101
// n & (n-1) = 0b0100 → NOT power of 2
 
console.log(isPowerOfTwo(1));   // true (2^0)
console.log(isPowerOfTwo(2));   // true (2^1)
console.log(isPowerOfTwo(3));   // false
console.log(isPowerOfTwo(16));  // true (2^4)
console.log(isPowerOfTwo(18));  // false
console.log(isPowerOfTwo(0));   // false (edge case!)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// Reverse the bits of a 32-bit unsigned integer
 
function reverseBits(n: number): number {
    // Swap adjacent single bits
    n = ((n & 0x55555555) << 1) | ((n >>> 1) & 0x55555555);
    // Swap adjacent pairs
    n = ((n & 0x33333333) << 2) | ((n >>> 2) & 0x33333333);
    // Swap adjacent nibbles
    n = ((n & 0x0F0F0F0F) << 4) | ((n >>> 4) & 0x0F0F0F0F);
    // Swap adjacent bytes
    n = ((n & 0x00FF00FF) << 8) | ((n >>> 8) & 0x00FF00FF);
    // Swap 16-bit halves
    n = (n << 16) | (n >>> 16);
    
    return n >>> 0;  // Ensure unsigned
}
 
// Test: reverse 0b10110000...00000001
const original = 0b10110000000000000000000000000001;
const reversed = reverseBits(original);
console.log("Original:", (original >>> 0).toString(2).padStart(32, '0'));
console.log("Reversed:", (reversed >>> 0).toString(2).padStart(32, '0'));
 
// Simple version for understanding
function reverseBitsSimple(n: number): number {
    let result = 0;
    for (let i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>>= 1;
    }
    return result >>> 0;
}

Interview Strategy

In interviews, start with a simple, correct solution before optimizing. For bit counting, the simple loop is perfectly acceptable. Only introduce clever techniques like Brian Kernighan's algorithm after explaining why it's an improvement. Correctness first, optimization second.

Operator Selection Decision Guide

When approaching a bit manipulation problem, use this decision framework to select the right operators:

Operator Selection Framework

•Need to EXTRACT or TEST bits? → Use AND with a mask. Bits matching 1s in mask are preserved.
•Need to SET bits to 1? → Use OR with a mask. Bits matching 1s in mask become 1.
•Need to CLEAR bits to 0? → Use AND with inverted mask: & ~mask.
•Need to TOGGLE bits? → Use XOR with a mask. Bits matching 1s in mask flip.
•Need to INVERT all bits? → Use NOT: ~value.
•Need to DETECT difference? → XOR non-zero if different. a ^ b !== 0.
•Need to find UNIQUE element? → XOR all elements. Duplicates cancel.
•Need to CREATE mask for lower n bits? → (1 << n) - 1.
•Need to CREATE mask with just bit n? → 1 << n.
•Need to CREATE mask without bit n? → ~(1 << n).

Quick Reference — What Do You Need?
Goal	Operator(s)	Pattern
Extract/Test	AND (&)	`value & mask`
Set/Combine	OR (\|)	`value \| mask`
Clear/Remove	AND + NOT	`value & ~mask`
Toggle/Flip	XOR (^)	`value ^ mask`
Invert all	NOT (~)	`~value`
Compare	XOR	`a ^ b` (0 if equal)
Negate	NOT + 1	`~value + 1`
Abs value	XOR + shift	`(n ^ mask) - mask`

Summary: Complete Bitwise Operator Mastery

Congratulations! You now have complete mastery of the fundamental bitwise operators. Let's consolidate everything:

Key Takeaways

•AND (&): Both bits must be 1. Use for masking, testing, clearing (with ~).
•OR (|): Either bit must be 1. Use for setting bits, combining flags.
•XOR (^): Bits must differ. Use for toggling, swapping, finding uniques.
•NOT (~): Flip all bits. Use for creating inverted masks. Remember ~n = -(n+1).
•Precedence: Bitwise operators have LOW precedence. Always use parentheses!
•Patterns: Master set/clear/toggle/test — they combine operators elegantly.
•Performance: Bitwise is fastest (1 cycle), but readability matters too.
•Practice: Interview problems frequently test bit manipulation skills.

Binary Operators
Op	Symbol	When
AND	&	Extract/Test
OR	\|	Combine/Set
XOR	^	Toggle/Diff

Unary Operator
Op	Symbol	When
NOT	~	Invert all

What's Next:

With complete mastery of the fundamental bitwise operators, you're ready to explore more advanced topics: bit shifting (left shift, right shift), common bit manipulation tricks, and specialized applications like bitmask dynamic programming. The foundation you've built here will serve you throughout your computing career.

Module Complete!

You have achieved complete mastery of the bitwise operators AND, OR, XOR, and NOT. You understand their truth tables, hardware origins, practical applications, and how to combine them for powerful bit manipulation. This knowledge is foundational for systems programming, algorithm optimization, and technical interviews. Excellent work!