AND — Both Bits Must Be 1 - Bitwise Operators — AND, OR, XOR, NOT | OneNoughtOne

0/364

Data Structures & AlgorithmsBitwise Operators — AND, OR, XOR, NOT

Bitwise Operators — AND, OR, XOR, NOT

LevelIntermediate

Duration75 mins

TopicBitwise Operators — AND, OR, XOR, NOT

1 / 5

AND — Both Bits Must Be 1

The Foundation of Digital Logic

At the heart of every computation your computer performs—from rendering complex 3D graphics to executing machine learning algorithms—lies a remarkably simple set of operations that manipulate individual bits. These bitwise operators are the most primitive building blocks of digital logic, directly corresponding to the physical gates etched into silicon chips.

The AND operator is perhaps the most intuitive of these operations. Its behavior mirrors a concept we encounter daily in natural language: for something to be true, both conditions must be met. Just as the statement "I will go to the movies if it's Saturday AND I have free time" requires both conditions to be satisfied, the bitwise AND requires both input bits to be 1 for the output to be 1.

What You Will Learn

By the end of this page, you will deeply understand how the AND operator works at the bit level, why it behaves the way it does from a hardware perspective, and how to leverage it for practical tasks like masking, clearing bits, checking bit status, and optimizing computations. You'll gain the foundational knowledge necessary to think at the bit level—a skill that separates casual programmers from systems-level engineers.

The AND Operator Defined

The bitwise AND operator, typically represented by the & symbol in most programming languages, performs a logical conjunction on each pair of corresponding bits from two operands. The result bit is 1 if and only if both input bits are 1; otherwise, the result is 0.

This definition, while precise, deserves deeper exploration to truly internalize its behavior.

The Core Principle

Think of AND as a strict gatekeeper. It only allows a 1 through when both inputs present a 1. Any other combination—(0,0), (0,1), or (1,0)—results in 0. This strictness is what makes AND invaluable for selective bit extraction and clearing operations.

Formal Definition:

Given two binary values A and B, the AND operation is defined as:

A AND B = 1 if A = 1 AND B = 1
A AND B = 0 otherwise

In mathematical notation, this can be expressed as logical multiplication:

A ∧ B = A × B (where A, B ∈ {0, 1})

This multiplicative interpretation is key: treating bits as 0 and 1, AND is literally multiplication. Zero times anything is zero; only 1 times 1 yields 1.

AND Truth Table
Bit A	Bit B	A AND B	Explanation
0	0	0	Neither bit is set → result is 0
0	1	0	First bit not set → result is 0
1	0	0	Second bit not set → result is 0
1	1	1	Both bits set → result is 1

Key Insight from the Truth Table:

Notice that three out of four possible input combinations result in 0. This asymmetry is fundamental to AND's utility—it's an exclusive operator that demands unanimous agreement. This property makes AND perfect for filtering and selective extraction operations.

Hardware Origins — The AND Gate

Understanding the AND operator requires appreciating its physical realization. In digital electronics, an AND gate is one of the fundamental logic gates from which all complex circuits are built.

Transistor-Level Implementation:

At the transistor level, an AND gate can be constructed using two transistors connected in series. For current to flow from input to output (representing a 1), both transistors must be in the "on" state. If either transistor is off, the circuit is broken and no current flows (representing a 0).

This physical constraint—that both switches must be closed for current to pass—is the hardware manifestation of the logical AND requirement.

      Voltage Source (+V)
             │
             │
        ┌────┴────┐
        │   A     │  ← Switch A (Transistor controlled by input A)
        │  (SW)   │
        └────┬────┘
             │
        ┌────┴────┐
        │   B     │  ← Switch B (Transistor controlled by input B)
        │  (SW)   │
        └────┬────┘
             │
             ▼
          OUTPUT
             │
             ▼
          Ground
 
If A = 1 AND B = 1 → Both switches closed → Current flows → Output = 1
If A = 0 OR  B = 0 → At least one switch open → No current → Output = 0

Boolean Algebra Foundation:

George Boole, a 19th-century mathematician, formalized the arithmetic of logic, laying the groundwork for digital computing nearly a century before the first electronic computers. Claude Shannon later showed that Boolean algebra could be implemented with electrical switches, connecting abstract logic to physical circuits.

The AND operation in Boolean algebra follows these laws:

Identity Law: A AND 1 = A (ANDing with 1 preserves the original value)
Null Law: A AND 0 = 0 (ANDing with 0 always yields 0)
Idempotent Law: A AND A = A (ANDing a value with itself yields that value)
Commutative Law: A AND B = B AND A (order doesn't matter)
Associative Law: (A AND B) AND C = A AND (B AND C) (grouping doesn't matter)

From Physics to Programs

When you write a & b in your code, you're ultimately triggering physical AND gates in the processor's Arithmetic Logic Unit (ALU). The compiler translates your high-level operation into machine instructions, which the CPU executes using actual transistor logic. Understanding this connection helps demystify "low-level" programming—it's physics all the way down.

Multi-Bit AND Operations

In practice, we rarely AND individual bits in isolation. Computers work with bytes (8 bits), words (16/32/64 bits), and larger data units. The bitwise AND operator applies the single-bit AND logic independently to each corresponding bit position of the two operands.

This parallel, position-wise application is crucial to understand: the AND at position 0 has no knowledge of what happens at position 7; each bit pair operates in complete isolation.

   Operand A:    1 0 1 1 0 1 1 0  (decimal: 182)
   Operand B:    1 1 0 1 1 0 1 0  (decimal: 218)
                 ─────────────────
   A AND B:      1 0 0 1 0 0 1 0  (decimal: 146)
 
Position-by-position breakdown:
  Position 7: 1 AND 1 = 1
  Position 6: 0 AND 1 = 0
  Position 5: 1 AND 0 = 0
  Position 4: 1 AND 1 = 1
  Position 3: 0 AND 1 = 0
  Position 2: 1 AND 0 = 0
  Position 1: 1 AND 1 = 1
  Position 0: 0 AND 0 = 0

Parallel Execution:

A critical advantage of bitwise operations is their inherent parallelism. Modern 64-bit processors perform all 64 bit-wise AND operations in a single clock cycle. This makes bitwise AND one of the fastest possible operations—typically executing in 1 CPU cycle with a throughput of one operation per cycle (or better, with modern superscalar architectures).

Compare this to operations like division, which can take 20-40 cycles. This performance differential is why bit manipulation is favored in performance-critical code.

1
2
3
4
5
6
7
8
9
10
11
12
13
// 8-bit integer AND operation
const a = 0b10110110; // 182 in decimal
const b = 0b11011010; // 218 in decimal
const result = a & b; // 0b10010010 = 146
 
console.log(result.toString(2).padStart(8, '0')); 
// Output: "10010010"
 
// 32-bit example - masking to extract lower 16 bits
const value = 0x12345678;        // Full 32-bit value
const mask = 0x0000FFFF;          // Lower 16 bits mask
const lower16 = value & mask;     // Extract lower 16 bits
console.log(lower16.toString(16)); // Output: "5678"

Mind the Bit Width

In languages like JavaScript, all numbers are 64-bit floating-point, but bitwise operations treat operands as 32-bit signed integers. This can lead to unexpected behavior with large numbers. In strongly-typed languages, be mindful of integer sizes (int8, int16, int32, int64) and signedness when performing bitwise operations.

Bit Masking — The Primary Use Case

The most important application of the AND operator is bit masking—selectively extracting or testing specific bits within a larger value. A mask is a carefully constructed bit pattern that, when ANDed with a target value, isolates the bits of interest.

The Masking Principle:

Recall the Boolean laws:

A AND 1 = A (1 preserves the original bit)
A AND 0 = 0 (0 clears the bit to zero)

By creating a mask with 1s in positions we want to keep and 0s in positions we want to discard, we can extract arbitrary bit fields from any value.

Goal: Extract bits 4-7 (the upper nibble of the lower byte)
 
Original Value:  1 1 0 0 1 0 1 1  0 1 1 0 0 1 0 1
                 ─────────────────────────────────
                 byte 1 (high)    byte 0 (low)
 
Mask:            0 0 0 0 0 0 0 0  1 1 1 1 0 0 0 0  (0x00F0)
                 ─────────────────────────────────
                 Zeros: discard   Ones: keep
 
Result:          0 0 0 0 0 0 0 0  0 1 1 0 0 0 0 0  (0x0060)
                                  ─────────
                                  Extracted bits!
 
The mask acts like a stencil, revealing only the bits where it has 1s.

Common Masking Patterns:

Experienced programmers internalize these patterns:

Pattern	Mask Expression	Purpose
`0x0F` (0b00001111)	`value & 0x0F`	Extract lower nibble (4 bits)
`0xF0` (0b11110000)	`value & 0xF0`	Extract upper nibble (8-bit)
`0xFF`	`value & 0xFF`	Extract lowest byte
`0xFFFF`	`value & 0xFFFF`	Extract lower 16 bits
`1 << n`	`value & (1 << n)`	Test if bit n is set
`~(1 << n)`	`value & ~(1 << n)`	Clear bit n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Example 1: Extracting color components from RGB value
const rgb = 0xFF5733; // Orange color
 
const red   = (rgb >> 16) & 0xFF; // Shift right 16, mask to 8 bits
const green = (rgb >> 8)  & 0xFF; // Shift right 8, mask to 8 bits  
const blue  =  rgb        & 0xFF; // Mask directly for lowest 8 bits
 
console.log({ red, green, blue }); 
// Output: { red: 255, green: 87, blue: 51 }
 
// Example 2: Extracting bit fields from a network packet header
const header = 0b11010110_01110011; // Fictional 16-bit header
 
const version   = (header >> 14) & 0b11;   // Top 2 bits: version
const flags     = (header >> 10) & 0b1111; // Next 4 bits: flags
const payloadLen = header & 0b1111111111;  // Bottom 10 bits: length
 
console.log({ version, flags, payloadLen });
// Output: { version: 3, flags: 5, payloadLen: 371 }

The Mask + Shift Pattern

When extracting bit fields that aren't at position 0, you typically need to shift then mask (or mask then shift). Shift brings your target bits to the lowest positions, then mask isolates them. This pattern appears constantly in systems programming, network protocol parsing, and hardware interfacing.

Checking Bit Status

One of the most frequent uses of AND is to test whether a specific bit is set (1) or clear (0). This is essential for:

Reading hardware status registers
Checking permission flags
Testing feature availability
Validating configuration states
Determining if a number has certain properties (even/odd, power of 2, etc.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Check if bit at position n is set
function isBitSet(value: number, n: number): boolean {
    const mask = 1 << n;  // Create mask with only bit n set
    return (value & mask) !== 0;
}
 
// Examples
const flags = 0b10110100;  // Decimal: 180
 
console.log(isBitSet(flags, 0)); // false (bit 0 = 0)
console.log(isBitSet(flags, 2)); // true  (bit 2 = 1)
console.log(isBitSet(flags, 4)); // true  (bit 4 = 1)
console.log(isBitSet(flags, 6)); // false (bit 6 = 0)
console.log(isBitSet(flags, 7)); // true  (bit 7 = 1)
 
// Alternative: Check if result equals the mask
// This ensures we get a boolean directly
function isBitSetAlt(value: number, n: number): boolean {
    return ((value >> n) & 1) === 1;  // Shift bit to position 0, mask with 1
}

Classic Application: Checking Even/Odd

The least significant bit (bit 0) determines whether an integer is even or odd:

If bit 0 is 0 → number is even (divisible by 2)
If bit 0 is 1 → number is odd

This is because bit 0 represents 2⁰ = 1 in binary. Even numbers have no "remainder 1" from division by 2.

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
// Traditional approach (uses division)
function isEvenTraditional(n: number): boolean {
    return n % 2 === 0;
}
 
// Bitwise approach (uses AND)
function isEvenBitwise(n: number): boolean {
    return (n & 1) === 0;
}
 
// Why bitwise is faster:
// - Modulo involves division (expensive: ~20-40 cycles)
// - AND is a single-cycle operation
// - For hot loops, this difference matters
 
// Test cases
[0, 1, 2, 3, 100, 99].forEach(n => {
    console.log(`${n}: ${isEvenBitwise(n) ? 'even' : 'odd'}`);
});
// Output: 0: even, 1: odd, 2: even, 3: odd, 100: even, 99: odd
 
// Caveat: For negative numbers in JavaScript, bitwise AND 
// works on the 32-bit two's complement representation.
// (n & 1) === 1 correctly identifies odd negative numbers.
console.log((-3 & 1) === 1); // true (−3 is odd)

When to Use Bitwise Even/Odd

While n & 1 is technically faster than n % 2, modern compilers often optimize the modulo to a bitwise AND anyway. Use the bitwise version when you're explicitly working in a bit-manipulation context or when readability isn't harmed. In most application code, clarity trumps micro-optimization.

Clearing Bits with AND

While AND is often used for extraction, it's equally powerful for clearing (setting to 0) specific bits while leaving others unchanged. This is achieved by ANDing with a mask that has 0s in the positions to clear and 1s everywhere else.

The Clearing Principle:

A AND 1 = A (bit preserved)
A AND 0 = 0 (bit cleared)

To clear bit n, we create a mask with all 1s except at position n, then AND.

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
// Clear bit at position n
function clearBit(value: number, n: number): number {
    const mask = ~(1 << n);  // All 1s except position n
    return value & mask;
}
 
// Visual example:
// value:    10110101 (decimal 181)
// 1 << 4:   00010000 (bit 4 set)
// ~(1 << 4): 11101111 (all bits EXCEPT bit 4)
// AND:      10100101 (decimal 165) — bit 4 cleared!
 
const original = 0b10110101; // 181
const cleared = clearBit(original, 4);
console.log(cleared.toString(2).padStart(8, '0')); 
// Output: "10100101" (165)
 
// Clear multiple bits at once
function clearBits(value: number, mask: number): number {
    return value & ~mask;  // Invert mask, then AND
}
 
// Clear bits 2, 3, and 4
const multiMask = 0b00011100; // Bits to clear
const result = clearBits(0b11111111, multiMask);
console.log(result.toString(2).padStart(8, '0'));
// Output: "11100011" — bits 2, 3, 4 are now 0

Real-World Application: Permissions and Flags

Systems often use bit flags to represent permissions, capabilities, or states. Clearing a bit corresponds to revoking a permission or disabling a feature.

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
// Define permission flags (each is a power of 2)
const Permissions = {
    READ:    0b0001,  // 1  - bit 0
    WRITE:   0b0010,  // 2  - bit 1
    EXECUTE: 0b0100,  // 4  - bit 2
    DELETE:  0b1000,  // 8  - bit 3
} as const;
 
// A user starts with all permissions
let userPerms = Permissions.READ | Permissions.WRITE | 
                Permissions.EXECUTE | Permissions.DELETE;
console.log(userPerms.toString(2)); // "1111" — all permissions
 
// Revoke WRITE permission using AND with inverted mask
userPerms = userPerms & ~Permissions.WRITE;
console.log(userPerms.toString(2)); // "1101" — WRITE removed
 
// Check if WRITE is still set
const hasWrite = (userPerms & Permissions.WRITE) !== 0;
console.log(hasWrite); // false — correctly revoked
 
// Revoke multiple permissions at once
const toRevoke = Permissions.EXECUTE | Permissions.DELETE;
userPerms = userPerms & ~toRevoke;
console.log(userPerms.toString(2)); // "0001" — only READ remains

The Clear Bit Pattern

The pattern value & ~mask is your go-to for clearing bits. Think of it as: "Keep everything NOT in the mask." The ~ inverts the mask, turning your 'bits to clear' into 'bits to keep', and AND does the filtering.

Extracting Bit Fields

A bit field is a contiguous sequence of bits within a larger value that represents a discrete piece of information. Extracting bit fields is fundamental to:

Network protocol parsing (IP headers, TCP flags)
File format decoding (image metadata, audio frames)
Hardware register manipulation (device configuration)
Packed data structures (compression, serialization)
Graphics programming (color channels, pixel formats)

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
/**
 * Extract a bit field from a value
 * @param value - The source value
 * @param startBit - The starting bit position (0-indexed, from LSB)
 * @param width - The number of bits in the field
 * @returns The extracted field value
 */
function extractBitField(
    value: number, 
    startBit: number, 
    width: number
): number {
    // Step 1: Create a mask with 'width' consecutive 1s
    // (1 << width) gives us 2^width, subtracting 1 gives width 1s
    const mask = (1 << width) - 1;
    
    // Step 2: Shift value right to bring field to position 0
    // Step 3: Apply mask to isolate the field
    return (value >> startBit) & mask;
}
 
// Example: Extract bits 4-7 (4 bits starting at position 4)
const data = 0b11011010_10110011; // 16-bit value
 
const field = extractBitField(data, 4, 4);
console.log(field.toString(2)); // "1011" (decimal 11)
 
// Visualization:
// data:          11011010 10110011
//                         ^^^^---- bits 4-7
// >> 4:          00001101 10101011
// mask (0xF):    00000000 00001111
// AND:           00000000 00001011  = 11 decimal

Practical Example: IPv4 Header Parsing

The IPv4 header is a classic example of packed bit fields. The first byte contains two 4-bit fields: the version (should be 4) and the Internet Header Length (IHL).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Simulated first byte of an IPv4 header
// Format: | Version (4 bits) | IHL (4 bits) |
const firstByte = 0b01000101; // 0x45 — very common
 
// Extract version (upper 4 bits: bits 4-7)
const version = (firstByte >> 4) & 0x0F;
console.log(`IP Version: ${version}`); // 4
 
// Extract IHL (lower 4 bits: bits 0-3)
const ihl = firstByte & 0x0F;
console.log(`IHL: ${ihl}`);  // 5 (header is 5×4 = 20 bytes)
 
// More complex: Extract Type of Service from second byte
const secondByte = 0b00011000; // DSCP=6, ECN=0
 
const dscp = (secondByte >> 2) & 0x3F; // 6 bits
const ecn = secondByte & 0x03;          // 2 bits
 
console.log(`DSCP: ${dscp}, ECN: ${ecn}`); // DSCP: 6, ECN: 0

Bit Field Best Practices

When working with bit fields: (1) Define named constants for field positions and widths, (2) Create reusable extraction/insertion functions, (3) Document the expected bit layout clearly, (4) Consider endianness when dealing with multi-byte values from external sources.

AND for Alignment and Rounding

A sophisticated use of AND is enforcing alignment by rounding down to a power-of-2 boundary. This is critical in:

Memory allocators (aligning allocations to cache lines)
File systems (aligning to block sizes)
Graphics (aligning to pixel grid boundaries)
Network buffers (aligning to packet boundaries)

The Insight:

To round down to a multiple of 2^n, we clear the lower n bits. This is because powers of 2 in binary have a single 1 bit followed by zeros—anything below that 1 is the "remainder" we want to discard.

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
/**
 * Round down to the nearest multiple of alignment
 * Alignment MUST be a power of 2
 */
function alignDown(value: number, alignment: number): number {
    // alignment - 1 gives us a mask of lower bits to clear
    // ~(alignment - 1) is all 1s except those lower bits
    // AND clears the lower bits, rounding down
    return value & ~(alignment - 1);
}
 
// Examples with 16-byte alignment (2^4 = 16)
console.log(alignDown(0, 16));   // 0
console.log(alignDown(15, 16));  // 0   (15 rounds down to 0)
console.log(alignDown(16, 16));  // 16  (already aligned)
console.log(alignDown(17, 16));  // 16  (17 rounds down to 16)
console.log(alignDown(31, 16));  // 16
console.log(alignDown(32, 16));  // 32
console.log(alignDown(100, 16)); // 96
 
// Why this works:
// alignment = 16 = 0b10000
// alignment - 1  = 0b01111 (lower 4 bits mask)
// ~(alignment-1) = 0b...11110000 (all 1s except lower 4)
//
// For value = 100 = 0b1100100
// 100 & 0b11110000 = 0b1100000 = 96

System-Level Examples:

Operating systems and memory allocators use this constantly:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Typical cache line size
#define CACHE_LINE_SIZE 64
 
// Align a pointer down to cache line boundary
void* align_to_cache_line(void* ptr) {
    uintptr_t addr = (uintptr_t)ptr;
    return (void*)(addr & ~(CACHE_LINE_SIZE - 1));
}
 
// Page size alignment (4KB pages)
#define PAGE_SIZE 4096
 
// Align address down to page boundary
uintptr_t page_align(uintptr_t addr) {
    return addr & ~(PAGE_SIZE - 1);  // Clear lower 12 bits
}
 
// This is faster than: (addr / PAGE_SIZE) * PAGE_SIZE
// Division is expensive; AND is a single cycle.

Power of 2 Requirement

The alignment AND trick ONLY works when alignment is a power of 2. For non-power-of-2 alignment, you must use integer division: (value / alignment) * alignment. This is a common source of bugs when arbitrary alignments are needed.

Summary: AND Operator Mastery

The AND operator, despite its apparent simplicity, is a remarkably versatile tool in the programmer's arsenal. Let's consolidate the key concepts:

Key Takeaways

•Core Behavior: AND returns 1 only when BOTH input bits are 1. This strictness makes it ideal for filtering and extraction.
•Truth Table Memory Aid: Think of AND as multiplication: 0×anything=0, only 1×1=1.
•Hardware Foundation: AND gates are fundamental building blocks; your & operation directly uses physical AND gates in the CPU.
•Bit Masking: Use AND with a mask to extract specific bits. 1s in the mask preserve bits; 0s clear them.
•Clearing Bits: Use value & ~mask to clear specific bits while preserving others.
•Testing Bits: Use value & (1 << n) to check if bit n is set.
•Even/Odd Check: n & 1 equals 0 for even numbers, 1 for odd numbers.
•Alignment: Round down to power-of-2 boundaries with value & ~(alignment - 1).

AND Operator Quick Reference
Operation	Expression	Notes
Check if bit n is set	`(value & (1 << n)) !== 0`	Returns boolean
Extract bit n as 0 or 1	`(value >> n) & 1`	Normalized to 0/1
Extract lower n bits	`value & ((1 << n) - 1)`	Mask with n ones
Clear bit n	`value & ~(1 << n)`	All 1s except bit n
Clear lower n bits	`value & ~((1 << n) - 1)`	Alignment use
Check even	`(value & 1) === 0`	Faster than modulo
Isolate lowest set bit	`value & (-value)`	Uses two's complement

What's Next:

With AND mastered, we'll explore the OR operator in the next page—its complementary operator that combines bits rather than filtering them. Together, AND and OR form the foundation for building complex bit manipulation logic.

Page Complete

You now have deep understanding of the AND bitwise operator—from its Boolean algebra roots to practical applications in masking, extraction, clearing, and alignment. This knowledge forms the foundation for all bit manipulation techniques we'll explore throughout this chapter.