Data Structures & AlgorithmsCommon Bit Manipulation Tricks

Common Bit Manipulation Tricks

LevelIntermediate

Duration75 mins

TopicCommon Bit Manipulation Tricks

4 / 5

Isolate a Specific Bit

Working with Bits at Any Position

In the previous pages, we focused on the rightmost set bit—a special position that's easy to work with due to properties of two's complement arithmetic. But real-world bit manipulation often requires working with bits at arbitrary positions.

Questions like:

Is bit 5 set in this number?
What is the value of bits 4-7?
Is the sign bit (bit 31) set?

To answer these, we need to master positional bit isolation—the technique of extracting or checking the value of a bit at a specific position. This is the foundation of bitmask programming, flag manipulation, and low-level systems work.

What You Will Learn

By the end of this page, you will understand how to create bit masks for any position using left shift, check if a specific bit is set using AND, extract the value of a bit (0 or 1), extract multi-bit fields from integers, and apply these techniques to real-world problems like permission systems and protocol parsing.

The Position Mask: 1 << k

The key to isolating a bit at position k is creating a mask with a single 1 at that position: 1 << k.

How left shift creates the mask:

The expression 1 << k shifts the single bit in 1 to the left by k positions:

1 << 0 = 00000001  (bit 0)
1 << 1 = 00000010  (bit 1)
1 << 2 = 00000100  (bit 2)
1 << 3 = 00001000  (bit 3)
1 << 4 = 00010000  (bit 4)
1 << 5 = 00100000  (bit 5)
1 << k = 2^k      (bit k)

Mathematical interpretation: $$1 << k = 2^k$$

The mask has value $2^k$, with exactly one bit set at position $k$ (0-indexed from the right).

Position Masks (8-bit examples)
k	1 << k	Binary	Decimal Value
0	1 << 0	00000001	1
1	1 << 1	00000010	2
2	1 << 2	00000100	4
3	1 << 3	00001000	8
4	1 << 4	00010000	16
5	1 << 5	00100000	32
6	1 << 6	01000000	64
7	1 << 7	10000000	128

Bit Position Convention

Bit positions are 0-indexed from the right (least significant bit). Position 0 is the rightmost bit (the 1s place), position 1 is the next bit (the 2s place), and so on. This matches the mathematical notation where bit k contributes 2^k to the value.

Check if a Specific Bit is Set

To check if bit k is set in number n, we AND with the positional mask:

$$\text{Bit } k \text{ is set} \Leftrightarrow (n & (1 << k)) \neq 0$$

Why this works:

The mask 1 << k has a 1 only at position k. When we AND:

If bit k in n is 1: The result has a 1 at position k (non-zero)
If bit k in n is 0: The result is all zeros

Example: Check if bit 2 is set in n = 12 (1100₂)

n        = 1100  (12)
1 << 2   = 0100  (4)
n & mask = 0100  (4, non-zero → bit 2 IS set)

Example: Check if bit 1 is set in n = 12 (1100₂)

n        = 1100  (12)
1 << 1   = 0010  (2)
n & mask = 0000  (0 → bit 1 is NOT set)

check_bit.py
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
def is_bit_set(n: int, k: int) -> bool:
    """
    Check if bit at position k (0-indexed from right) is set.
    
    Time: O(1)
    Space: O(1)
    
    Args:
        n: The number to check
        k: The bit position (0 = rightmost)
    
    Returns:
        True if bit k is set (1), False if unset (0)
    
    Examples:
        is_bit_set(12, 2)  # True  (12 = 1100, bit 2 is set)
        is_bit_set(12, 1)  # False (12 = 1100, bit 1 is not set)
        is_bit_set(12, 3)  # True  (12 = 1100, bit 3 is set)
    """
    return (n & (1 << k)) != 0
 
 
def is_bit_set_bool(n: int, k: int) -> bool:
    """
    Alternative: Use right shift to get boolean directly.
    Shifts bit k to position 0, then ANDs with 1.
    """
    return ((n >> k) & 1) == 1
 
 
def get_bit_value(n: int, k: int) -> int:
    """
    Get the actual value (0 or 1) of bit at position k.
    More explicit about returning 0 or 1, not just truthy/falsy.
    """
    return (n >> k) & 1
 
 
# Demonstration
print("=== Check Specific Bit ===\n")
 
n = 42  # Binary: 101010
print(f"Number: {n} = {bin(n)} = {format(n, '08b')}")
print()
 
print("Checking each bit position:")
for k in range(8):
    is_set = is_bit_set(n, k)
    value = get_bit_value(n, k)
    mask = 1 << k
    indicator = "✓" if is_set else " "
    print(f"  Bit {k}: {indicator} (n & {mask:3}) = {n & mask:3}, value = {value}")
 
print()
 
# Verify both methods give same result
print("Verifying methods are equivalent:")
for n in range(256):
    for k in range(8):
        assert is_bit_set(n, k) == is_bit_set_bool(n, k)
print("✓ All checks passed!")

Two Methods: AND-Mask vs Shift-and-Mask

There are two common ways to check/extract a bit at position k:

Method 1: AND with shifted mask

(n & (1 << k)) != 0   // Check if bit is set
(n & (1 << k)) >> k   // Get value (0 or 1)

Method 2: Shift then mask

(n >> k) & 1          // Shift bit to position 0, then mask

Both methods work correctly. Let's compare them:

Method 1: (n & (1 << k))

•Result: 0 or 2^k
•Semantics: Returns the weighted bit value
•Truth test: Non-zero means bit is set
•Use case: When you want the actual contribution of that bit
•Example: n=12, k=2 → result is 4

Method 2: (n >> k) & 1

•Result: 0 or 1
•Semantics: Returns the raw bit value
•Truth test: 1 means bit is set
•Use case: When you just need 0 or 1
•Example: n=12, k=2 → result is 1

methods_comparison.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Comparison of the two methods
 
n = 42  # Binary: 101010
 
print(f"n = {n} ({bin(n)})")
print()
 
print("Method | k | n & (1<<k) | (n>>k) & 1 | Both True?")
print("-" * 55)
 
for k in range(6):
    method1 = n & (1 << k)        # Returns 0 or 2^k
    method2 = (n >> k) & 1        # Returns 0 or 1
    both_true = bool(method1) == bool(method2)
    
    print(f"       | {k} | {method1:10} | {method2:10} | {both_true}")
 
print()
print("Key insight: Method 1 gives the WEIGHTED value (0 or 2^k)")
print("             Method 2 gives the RAW bit (0 or 1)")
print()
print("For boolean checks, both work identically.")
print("For extracting the actual bit value, Method 2 is cleaner.")

Which to Use?

Use (n >> k) & 1 when you need the actual 0/1 bit value (e.g., for building binary strings, extracting fields). Use n & (1 << k) when you're testing in an if-statement (both work, but some find != 0 explicit) or when you actually want the weighted value 2^k.

Extracting Multi-Bit Fields

Often we need to extract not just a single bit, but a range of bits—a field. For example, extracting bits 4-7 from a 32-bit integer.

The general formula:

$$\text{Extract bits } [start, end] = (n >> start) & \text{mask}$$

Where mask has 1s in the positions we want:

mask = (1 << width) - 1 where width = end - start + 1

Example: Extract bits 2-4 from n = 78 (binary: 01001110)

Bits 2-4 are: 011 = 3

n          = 01001110  (78)
n >> 2     = 00010011  (shift bit 2 to position 0)
mask       = 00000111  ((1 << 3) - 1 = 7, for 3 bits)
result     = 00000011  (3)

extract_field.py
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
def extract_bits(n: int, start: int, width: int) -> int:
    """
    Extract 'width' bits starting from position 'start'.
    
    Args:
        n: The number to extract from
        start: Starting bit position (0-indexed, rightmost)
        width: Number of bits to extract
    
    Returns:
        The extracted bits as an integer
    
    Example:
        extract_bits(0b11001110, 2, 3)  # Returns 0b011 = 3
        (Bits 2, 3, 4 from 11001110 are 011)
    """
    mask = (1 << width) - 1  # Create mask with 'width' 1s
    return (n >> start) & mask
 
 
def extract_bits_visual(n: int, start: int, width: int) -> int:
    """Same as above but with visualization."""
    mask = (1 << width) - 1
    shifted = n >> start
    result = shifted & mask
    
    bits = 8  # Display width
    print(f"n         = {format(n, f'0{bits}b')} ({n})")
    print(f"n >> {start}    = {format(shifted & ((1 << bits) - 1), f'0{bits}b')} (shifted)")
    print(f"mask      = {format(mask, f'0{bits}b')} ((1 << {width}) - 1 = {mask})")
    print(f"result    = {format(result, f'0{bits}b')} ({result})")
    print()
    return result
 
 
# Demonstration
print("=== Extract Multi-Bit Fields ===\n")
 
# Example 1: Extract bits 2-4 from 78
print("Example 1: Extract bits 2-4 (width=3) from 78")
result = extract_bits_visual(78, 2, 3)
 
# Example 2: Extract bits 4-7 from 0xAB
print("Example 2: Extract bits 4-7 (width=4) from 0xAB (171)")
result = extract_bits_visual(0xAB, 4, 4)
 
# Example 3: Common use - extract a byte from a 32-bit word
print("Example 3: Extract second byte (bits 8-15) from 0x12345678")
word = 0x12345678
byte2 = extract_bits(word, 8, 8)
print(f"Word: 0x{word:08X}")
print(f"Second byte (bits 8-15): 0x{byte2:02X} ({byte2})")
print()
 
 
# Practical application: Parse an IP address from 32-bit integer
def parse_ipv4(ip_int: int) -> str:
    """Parse a 32-bit integer as an IPv4 address."""
    octets = [
        extract_bits(ip_int, 24, 8),  # First octet (bits 24-31)
        extract_bits(ip_int, 16, 8),  # Second octet (bits 16-23)
        extract_bits(ip_int, 8, 8),   # Third octet (bits 8-15)
        extract_bits(ip_int, 0, 8),   # Fourth octet (bits 0-7)
    ]
    return '.'.join(str(o) for o in octets)
 
 
print("Practical Example: Parse IPv4 from 32-bit integer")
ip_int = 0xC0A80001  # 192.168.0.1
print(f"Integer: 0x{ip_int:08X} ({ip_int})")
print(f"IPv4: {parse_ipv4(ip_int)}")

Real-World Application: Permission Systems

A classic application of bit isolation is permission systems. Instead of storing multiple boolean flags in separate variables, we pack them into a single integer. Each bit represents a different permission.

Example: Unix-style file permissions

Bit 0: Execute (x)
Bit 1: Write (w)
Bit 2: Read (r)

Permission 5 (101) = read + execute
Permission 7 (111) = read + write + execute
Permission 6 (110) = read + write
Permission 4 (100) = read only

This approach is incredibly space-efficient and allows checking multiple permissions with single bitwise operations.

permissions.py
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
# Permission system using bit flags
 
# Define permission bits as powers of 2
PERM_EXECUTE = 1 << 0  # 001 = 1
PERM_WRITE   = 1 << 1  # 010 = 2
PERM_READ    = 1 << 2  # 100 = 4
 
# Alternatively, use an enum
from enum import IntFlag
 
class Permission(IntFlag):
    EXECUTE = 1 << 0  # 1
    WRITE   = 1 << 1  # 2
    READ    = 1 << 2  # 4
    
    # Composite permissions
    READ_WRITE = READ | WRITE          # 6
    READ_EXECUTE = READ | EXECUTE      # 5
    ALL = READ | WRITE | EXECUTE       # 7
 
 
def has_permission(user_perms: int, required: int) -> bool:
    """Check if user has ALL the required permissions."""
    return (user_perms & required) == required
 
 
def has_any_permission(user_perms: int, any_of: int) -> bool:
    """Check if user has ANY of the permissions."""
    return (user_perms & any_of) != 0
 
 
def describe_permissions(perms: int) -> str:
    """Human-readable permission string."""
    r = 'r' if (perms & Permission.READ) else '-'
    w = 'w' if (perms & Permission.WRITE) else '-'
    x = 'x' if (perms & Permission.EXECUTE) else '-'
    return f"{r}{w}{x}"
 
 
# Demonstration
print("=== Permission System ===\n")
 
# User with read and execute permissions
user_perms = Permission.READ | Permission.EXECUTE  # 5 = 101
print(f"User permissions: {user_perms} ({bin(user_perms)}) = {describe_permissions(user_perms)}")
print()
 
# Check various permissions
checks = [
    (Permission.READ, "Read"),
    (Permission.WRITE, "Write"),
    (Permission.EXECUTE, "Execute"),
    (Permission.READ_WRITE, "Read+Write"),
    (Permission.ALL, "All"),
]
 
print("Permission checks (has ALL):")
for perm, name in checks:
    result = has_permission(user_perms, perm)
    indicator = "✓" if result else "✗"
    print(f"  {indicator} {name}: {result}")
 
print()
print("Permission checks (has ANY):")
for perm, name in checks:
    result = has_any_permission(user_perms, perm)
    indicator = "✓" if result else "✗"
    print(f"  {indicator} {name}: {result}")
 
print()
 
# All possible permission combinations
print("All permission combinations:")
for p in range(8):
    print(f"  {p} = {format(p, '03b')} = {describe_permissions(p)}")

Why Use Bit Flags?

Space efficiency: 32 boolean flags in a single 32-bit integer. 2) Fast combination: OR permissions together in O(1). 3) Fast checking: AND to check multiple permissions at once. 4) Easy serialization: Just store/transmit the integer. This pattern is used in file systems, network protocols, game engines, and countless other systems.

Application: Protocol and Data Format Parsing

Network protocols and binary file formats often pack multiple fields into compact bit representations. Understanding bit isolation is essential for parsing and constructing these formats.

Example: TCP Header Flags

The TCP header contains a 6-bit flags field:

Bit 0: FIN (Finish)
Bit 1: SYN (Synchronize)
Bit 2: RST (Reset)
Bit 3: PSH (Push)
Bit 4: ACK (Acknowledgment)
Bit 5: URG (Urgent)

Example: Color Packing (RGB565)

Some displays use 16-bit color with 5 bits red, 6 bits green, 5 bits blue:

Bits 0-4:   Blue (5 bits, 0-31)
Bits 5-10:  Green (6 bits, 0-63)
Bits 11-15: Red (5 bits, 0-31)

protocol_parsing.py
Python
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
# Example: RGB565 Color Format (16-bit color)
 
def extract_bits(n: int, start: int, width: int) -> int:
    """Extract 'width' bits starting at 'start' position."""
    mask = (1 << width) - 1
    return (n >> start) & mask
 
 
def pack_rgb565(r: int, g: int, b: int) -> int:
    """
    Pack RGB values into 16-bit RGB565 format.
    
    Args:
        r: Red (0-31, 5 bits)
        g: Green (0-63, 6 bits)
        b: Blue (0-31, 5 bits)
    """
    return ((r & 0x1F) << 11) | ((g & 0x3F) << 5) | (b & 0x1F)
 
 
def unpack_rgb565(rgb565: int) -> tuple:
    """
    Unpack 16-bit RGB565 color into R, G, B components.
    
    Returns:
        Tuple of (red, green, blue)
    """
    r = extract_bits(rgb565, 11, 5)  # Bits 11-15
    g = extract_bits(rgb565, 5, 6)   # Bits 5-10
    b = extract_bits(rgb565, 0, 5)   # Bits 0-4
    return (r, g, b)
 
 
def rgb565_to_rgb888(rgb565: int) -> tuple:
    """Convert RGB565 to RGB888 (standard 8-bit per channel)."""
    r, g, b = unpack_rgb565(rgb565)
    # Scale up: 5-bit (0-31) to 8-bit (0-255)
    r8 = (r * 255) // 31
    g8 = (g * 255) // 63
    b8 = (b * 255) // 31
    return (r8, g8, b8)
 
 
# Demonstration
print("=== RGB565 Color Format ===\n")
 
# Pack a color
red, green, blue = 31, 63, 31  # Max values = White
white = pack_rgb565(red, green, blue)
print(f"Pack RGB({red}, {green}, {blue}) = 0x{white:04X} ({white})")
print(f"Binary: {format(white, '016b')}")
print()
 
# Unpack it
r, g, b = unpack_rgb565(white)
print(f"Unpack 0x{white:04X} = RGB({r}, {g}, {b})")
print()
 
# Convert some colors
test_colors = [
    (31, 0, 0, "Red"),
    (0, 63, 0, "Green"),
    (0, 0, 31, "Blue"),
    (31, 63, 31, "White"),
    (0, 0, 0, "Black"),
    (15, 31, 15, "Gray"),
]
 
print("Color conversions:")
print("RGB565   | Packed     | Binary            | RGB888")
print("-" * 65)
for r, g, b, name in test_colors:
    packed = pack_rgb565(r, g, b)
    r8, g8, b8 = rgb565_to_rgb888(packed)
    print(f"{name:8} | 0x{packed:04X}     | {format(packed, '016b')} | ({r8:3}, {g8:3}, {b8:3})")
 
 
print()
print("=== TCP Flags Example ===\n")
 
# TCP flags
TCP_FIN = 1 << 0  # 0x01
TCP_SYN = 1 << 1  # 0x02
TCP_RST = 1 << 2  # 0x04
TCP_PSH = 1 << 3  # 0x08
TCP_ACK = 1 << 4  # 0x10
TCP_URG = 1 << 5  # 0x20
 
def parse_tcp_flags(flags: int) -> dict:
    """Parse TCP flags byte into individual flags."""
    return {
        'FIN': bool(flags & TCP_FIN),
        'SYN': bool(flags & TCP_SYN),
        'RST': bool(flags & TCP_RST),
        'PSH': bool(flags & TCP_PSH),
        'ACK': bool(flags & TCP_ACK),
        'URG': bool(flags & TCP_URG),
    }
 
# SYN-ACK packet
syn_ack = TCP_SYN | TCP_ACK  # 0x12
print(f"SYN-ACK flags: 0x{syn_ack:02X} ({format(syn_ack, '06b')})")
print(f"Parsed: {parse_tcp_flags(syn_ack)}")

Edge Cases and Best Practices

When working with bit positions, several edge cases and best practices are worth noting:

Watch Out For

•Bit width limits — For 32-bit integers, positions 0-31 are valid. Position 32+ may give unexpected results (undefined in C/C++, wrapped in some languages).
•Signed integers — Right-shifting signed negative numbers may be arithmetic (preserves sign) or logical (fills with zeros) depending on the language. Use unsigned integers when possible.
•JavaScript 32-bit limit — JavaScript bitwise operators work on 32-bit integers. For larger values, use BigInt.
•Off-by-one errors — Remember that positions are 0-indexed. Bit 0 is the rightmost bit, not bit 1.
•Endianness — When parsing multi-byte data from files/networks, consider byte order (big-endian vs. little-endian).

edge_cases.py
Python
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
# Edge cases demonstration
 
print("=== Edge Cases ===\n")
 
# 1. Check valid bit range
def is_bit_set_safe(n: int, k: int, bit_width: int = 32) -> bool:
    """Safe bit check with bounds validation."""
    if k < 0 or k >= bit_width:
        raise ValueError(f"Bit position {k} out of range [0, {bit_width - 1}]")
    return (n & (1 << k)) != 0
 
# 2. Negative numbers and right shift
print("Right shift behavior with negative numbers:")
n = -1  # All bits set in two's complement
print(f"n = {n} (binary: all 1s in two's complement)")
for k in range(4):
    # In Python, >> is always arithmetic (fills with sign bit)
    result = (n >> k) & 1
    print(f"  Bit {k}: {result}")
 
print()
 
# 3. Demonstrate large shift
print("Large shift values:")
n = 5
for k in [0, 2, 31, 32, 64]:
    try:
        # In Python, this works for any k (Python has arbitrary precision)
        result = n & (1 << k)
        print(f"  5 & (1 << {k:2}) = {result}")
    except Exception as e:
        print(f"  5 & (1 << {k:2}) = Error: {e}")
 
print()
 
# 4. Best practice: Define constants for common bit widths
class BitWidth:
    BYTE = 8
    SHORT = 16
    INT = 32
    LONG = 64
 
def get_bit_safe(n: int, k: int, width: int = BitWidth.INT) -> int:
    """Get bit value with explicit width checking."""
    assert 0 <= k < width, f"Position {k} invalid for {width}-bit integer"
    return (n >> k) & 1
 
# 5. Useful utility: get binary string with grouping
def format_binary(n: int, width: int = 8, group: int = 4) -> str:
    """Format number as binary with space-separated groups."""
    bits = format(n & ((1 << width) - 1), f'0{width}b')
    groups = [bits[i:i+group] for i in range(0, len(bits), group)]
    return ' '.join(groups)
 
print("Formatted binary:")
for n in [0, 1, 15, 255, 0xABCD]:
    print(f"  {n:5} = {format_binary(n, 16)}")

Language-Specific Behavior

In C/C++, shifting by more than the bit width is undefined behavior. In Python, arbitrary-precision integers support any shift. JavaScript converts to 32-bit before shifting. Always know your language's rules and consider using explicit bounds checking in production code.

Summary and Key Takeaways

We've learned to work with bits at arbitrary positions—a fundamental skill for systems programming, protocol implementation, and low-level optimization. Let's consolidate the key insights:

Key Takeaways

•Position mask: 1 << k — Creates a mask with a single 1 at position k, value = 2^k.
•Check bit: (n & (1 << k)) != 0 — Tests if bit k is set.
•Get bit value: (n >> k) & 1 — Extracts the 0 or 1 value at position k.
•Extract field: (n >> start) & ((1 << width) - 1) — Extracts multi-bit fields.
•Permission systems — Bit flags enable efficient, elegant boolean flag management.
•Protocol parsing — Essential for working with binary data formats and network protocols.

What's Next:

We've learned to check and extract bits. In the final page of this module, we'll complete the toolkit by learning to set, clear, and toggle bits at specific positions. These write operations, combined with the read operations from this page, give you complete control over individual bits.

Page Complete

You now understand how to isolate and extract bits at any position. This skill is fundamental to systems programming, protocol implementation, and efficient data packing. Next, we'll learn the complementary operations: setting, clearing, and toggling bits to modify values at specific positions.

4 / 5

Loading learning content...

Data Structures & AlgorithmsCommon Bit Manipulation Tricks

Common Bit Manipulation Tricks

LevelIntermediate

Duration75 mins

TopicCommon Bit Manipulation Tricks

4 / 5

Isolate a Specific Bit

Working with Bits at Any Position

Questions like:

Is bit 5 set in this number?
What is the value of bits 4-7?
Is the sign bit (bit 31) set?

What You Will Learn

The Position Mask: 1 << k

The key to isolating a bit at position k is creating a mask with a single 1 at that position: 1 << k.

How left shift creates the mask:

The expression 1 << k shifts the single bit in 1 to the left by k positions:

1 << 0 = 00000001  (bit 0)
1 << 1 = 00000010  (bit 1)
1 << 2 = 00000100  (bit 2)
1 << 3 = 00001000  (bit 3)
1 << 4 = 00010000  (bit 4)
1 << 5 = 00100000  (bit 5)
1 << k = 2^k      (bit k)

Mathematical interpretation: $$1 << k = 2^k$$

The mask has value $2^k$, with exactly one bit set at position $k$ (0-indexed from the right).

Position Masks (8-bit examples)
k	1 << k	Binary	Decimal Value
0	1 << 0	00000001	1
1	1 << 1	00000010	2
2	1 << 2	00000100	4
3	1 << 3	00001000	8
4	1 << 4	00010000	16
5	1 << 5	00100000	32
6	1 << 6	01000000	64
7	1 << 7	10000000	128

Bit Position Convention

Check if a Specific Bit is Set

To check if bit k is set in number n, we AND with the positional mask:

$$\text{Bit } k \text{ is set} \Leftrightarrow (n & (1 << k)) \neq 0$$

Why this works:

The mask 1 << k has a 1 only at position k. When we AND:

If bit k in n is 1: The result has a 1 at position k (non-zero)
If bit k in n is 0: The result is all zeros

Example: Check if bit 2 is set in n = 12 (1100₂)

n        = 1100  (12)
1 << 2   = 0100  (4)
n & mask = 0100  (4, non-zero → bit 2 IS set)

Example: Check if bit 1 is set in n = 12 (1100₂)

n        = 1100  (12)
1 << 1   = 0010  (2)
n & mask = 0000  (0 → bit 1 is NOT set)

check_bit.py
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
def is_bit_set(n: int, k: int) -> bool:
    """
    Check if bit at position k (0-indexed from right) is set.
    
    Time: O(1)
    Space: O(1)
    
    Args:
        n: The number to check
        k: The bit position (0 = rightmost)
    
    Returns:
        True if bit k is set (1), False if unset (0)
    
    Examples:
        is_bit_set(12, 2)  # True  (12 = 1100, bit 2 is set)
        is_bit_set(12, 1)  # False (12 = 1100, bit 1 is not set)
        is_bit_set(12, 3)  # True  (12 = 1100, bit 3 is set)
    """
    return (n & (1 << k)) != 0
 
 
def is_bit_set_bool(n: int, k: int) -> bool:
    """
    Alternative: Use right shift to get boolean directly.
    Shifts bit k to position 0, then ANDs with 1.
    """
    return ((n >> k) & 1) == 1
 
 
def get_bit_value(n: int, k: int) -> int:
    """
    Get the actual value (0 or 1) of bit at position k.
    More explicit about returning 0 or 1, not just truthy/falsy.
    """
    return (n >> k) & 1
 
 
# Demonstration
print("=== Check Specific Bit ===\n")
 
n = 42  # Binary: 101010
print(f"Number: {n} = {bin(n)} = {format(n, '08b')}")
print()
 
print("Checking each bit position:")
for k in range(8):
    is_set = is_bit_set(n, k)
    value = get_bit_value(n, k)
    mask = 1 << k
    indicator = "✓" if is_set else " "
    print(f"  Bit {k}: {indicator} (n & {mask:3}) = {n & mask:3}, value = {value}")
 
print()
 
# Verify both methods give same result
print("Verifying methods are equivalent:")
for n in range(256):
    for k in range(8):
        assert is_bit_set(n, k) == is_bit_set_bool(n, k)
print("✓ All checks passed!")

Two Methods: AND-Mask vs Shift-and-Mask

There are two common ways to check/extract a bit at position k:

Method 1: AND with shifted mask

(n & (1 << k)) != 0   // Check if bit is set
(n & (1 << k)) >> k   // Get value (0 or 1)

Method 2: Shift then mask

(n >> k) & 1          // Shift bit to position 0, then mask

Both methods work correctly. Let's compare them:

Method 1: (n & (1 << k))

•Result: 0 or 2^k
•Semantics: Returns the weighted bit value
•Truth test: Non-zero means bit is set
•Use case: When you want the actual contribution of that bit
•Example: n=12, k=2 → result is 4

Method 2: (n >> k) & 1

•Result: 0 or 1
•Semantics: Returns the raw bit value
•Truth test: 1 means bit is set
•Use case: When you just need 0 or 1
•Example: n=12, k=2 → result is 1

methods_comparison.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Comparison of the two methods
 
n = 42  # Binary: 101010
 
print(f"n = {n} ({bin(n)})")
print()
 
print("Method | k | n & (1<<k) | (n>>k) & 1 | Both True?")
print("-" * 55)
 
for k in range(6):
    method1 = n & (1 << k)        # Returns 0 or 2^k
    method2 = (n >> k) & 1        # Returns 0 or 1
    both_true = bool(method1) == bool(method2)
    
    print(f"       | {k} | {method1:10} | {method2:10} | {both_true}")
 
print()
print("Key insight: Method 1 gives the WEIGHTED value (0 or 2^k)")
print("             Method 2 gives the RAW bit (0 or 1)")
print()
print("For boolean checks, both work identically.")
print("For extracting the actual bit value, Method 2 is cleaner.")

Which to Use?

Extracting Multi-Bit Fields

Often we need to extract not just a single bit, but a range of bits—a field. For example, extracting bits 4-7 from a 32-bit integer.

The general formula:

$$\text{Extract bits } [start, end] = (n >> start) & \text{mask}$$

Where mask has 1s in the positions we want:

mask = (1 << width) - 1 where width = end - start + 1

Example: Extract bits 2-4 from n = 78 (binary: 01001110)

Bits 2-4 are: 011 = 3

n          = 01001110  (78)
n >> 2     = 00010011  (shift bit 2 to position 0)
mask       = 00000111  ((1 << 3) - 1 = 7, for 3 bits)
result     = 00000011  (3)

extract_field.py
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
def extract_bits(n: int, start: int, width: int) -> int:
    """
    Extract 'width' bits starting from position 'start'.
    
    Args:
        n: The number to extract from
        start: Starting bit position (0-indexed, rightmost)
        width: Number of bits to extract
    
    Returns:
        The extracted bits as an integer
    
    Example:
        extract_bits(0b11001110, 2, 3)  # Returns 0b011 = 3
        (Bits 2, 3, 4 from 11001110 are 011)
    """
    mask = (1 << width) - 1  # Create mask with 'width' 1s
    return (n >> start) & mask
 
 
def extract_bits_visual(n: int, start: int, width: int) -> int:
    """Same as above but with visualization."""
    mask = (1 << width) - 1
    shifted = n >> start
    result = shifted & mask
    
    bits = 8  # Display width
    print(f"n         = {format(n, f'0{bits}b')} ({n})")
    print(f"n >> {start}    = {format(shifted & ((1 << bits) - 1), f'0{bits}b')} (shifted)")
    print(f"mask      = {format(mask, f'0{bits}b')} ((1 << {width}) - 1 = {mask})")
    print(f"result    = {format(result, f'0{bits}b')} ({result})")
    print()
    return result
 
 
# Demonstration
print("=== Extract Multi-Bit Fields ===\n")
 
# Example 1: Extract bits 2-4 from 78
print("Example 1: Extract bits 2-4 (width=3) from 78")
result = extract_bits_visual(78, 2, 3)
 
# Example 2: Extract bits 4-7 from 0xAB
print("Example 2: Extract bits 4-7 (width=4) from 0xAB (171)")
result = extract_bits_visual(0xAB, 4, 4)
 
# Example 3: Common use - extract a byte from a 32-bit word
print("Example 3: Extract second byte (bits 8-15) from 0x12345678")
word = 0x12345678
byte2 = extract_bits(word, 8, 8)
print(f"Word: 0x{word:08X}")
print(f"Second byte (bits 8-15): 0x{byte2:02X} ({byte2})")
print()
 
 
# Practical application: Parse an IP address from 32-bit integer
def parse_ipv4(ip_int: int) -> str:
    """Parse a 32-bit integer as an IPv4 address."""
    octets = [
        extract_bits(ip_int, 24, 8),  # First octet (bits 24-31)
        extract_bits(ip_int, 16, 8),  # Second octet (bits 16-23)
        extract_bits(ip_int, 8, 8),   # Third octet (bits 8-15)
        extract_bits(ip_int, 0, 8),   # Fourth octet (bits 0-7)
    ]
    return '.'.join(str(o) for o in octets)
 
 
print("Practical Example: Parse IPv4 from 32-bit integer")
ip_int = 0xC0A80001  # 192.168.0.1
print(f"Integer: 0x{ip_int:08X} ({ip_int})")
print(f"IPv4: {parse_ipv4(ip_int)}")

Real-World Application: Permission Systems

Example: Unix-style file permissions

Bit 0: Execute (x)
Bit 1: Write (w)
Bit 2: Read (r)

Permission 5 (101) = read + execute
Permission 7 (111) = read + write + execute
Permission 6 (110) = read + write
Permission 4 (100) = read only

This approach is incredibly space-efficient and allows checking multiple permissions with single bitwise operations.

permissions.py
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
# Permission system using bit flags
 
# Define permission bits as powers of 2
PERM_EXECUTE = 1 << 0  # 001 = 1
PERM_WRITE   = 1 << 1  # 010 = 2
PERM_READ    = 1 << 2  # 100 = 4
 
# Alternatively, use an enum
from enum import IntFlag
 
class Permission(IntFlag):
    EXECUTE = 1 << 0  # 1
    WRITE   = 1 << 1  # 2
    READ    = 1 << 2  # 4
    
    # Composite permissions
    READ_WRITE = READ | WRITE          # 6
    READ_EXECUTE = READ | EXECUTE      # 5
    ALL = READ | WRITE | EXECUTE       # 7
 
 
def has_permission(user_perms: int, required: int) -> bool:
    """Check if user has ALL the required permissions."""
    return (user_perms & required) == required
 
 
def has_any_permission(user_perms: int, any_of: int) -> bool:
    """Check if user has ANY of the permissions."""
    return (user_perms & any_of) != 0
 
 
def describe_permissions(perms: int) -> str:
    """Human-readable permission string."""
    r = 'r' if (perms & Permission.READ) else '-'
    w = 'w' if (perms & Permission.WRITE) else '-'
    x = 'x' if (perms & Permission.EXECUTE) else '-'
    return f"{r}{w}{x}"
 
 
# Demonstration
print("=== Permission System ===\n")
 
# User with read and execute permissions
user_perms = Permission.READ | Permission.EXECUTE  # 5 = 101
print(f"User permissions: {user_perms} ({bin(user_perms)}) = {describe_permissions(user_perms)}")
print()
 
# Check various permissions
checks = [
    (Permission.READ, "Read"),
    (Permission.WRITE, "Write"),
    (Permission.EXECUTE, "Execute"),
    (Permission.READ_WRITE, "Read+Write"),
    (Permission.ALL, "All"),
]
 
print("Permission checks (has ALL):")
for perm, name in checks:
    result = has_permission(user_perms, perm)
    indicator = "✓" if result else "✗"
    print(f"  {indicator} {name}: {result}")
 
print()
print("Permission checks (has ANY):")
for perm, name in checks:
    result = has_any_permission(user_perms, perm)
    indicator = "✓" if result else "✗"
    print(f"  {indicator} {name}: {result}")
 
print()
 
# All possible permission combinations
print("All permission combinations:")
for p in range(8):
    print(f"  {p} = {format(p, '03b')} = {describe_permissions(p)}")

Why Use Bit Flags?

Space efficiency: 32 boolean flags in a single 32-bit integer. 2) Fast combination: OR permissions together in O(1). 3) Fast checking: AND to check multiple permissions at once. 4) Easy serialization: Just store/transmit the integer. This pattern is used in file systems, network protocols, game engines, and countless other systems.

Application: Protocol and Data Format Parsing

Network protocols and binary file formats often pack multiple fields into compact bit representations. Understanding bit isolation is essential for parsing and constructing these formats.

Example: TCP Header Flags

The TCP header contains a 6-bit flags field:

Bit 0: FIN (Finish)
Bit 1: SYN (Synchronize)
Bit 2: RST (Reset)
Bit 3: PSH (Push)
Bit 4: ACK (Acknowledgment)
Bit 5: URG (Urgent)

Example: Color Packing (RGB565)

Some displays use 16-bit color with 5 bits red, 6 bits green, 5 bits blue:

Bits 0-4:   Blue (5 bits, 0-31)
Bits 5-10:  Green (6 bits, 0-63)
Bits 11-15: Red (5 bits, 0-31)

protocol_parsing.py
Python
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
# Example: RGB565 Color Format (16-bit color)
 
def extract_bits(n: int, start: int, width: int) -> int:
    """Extract 'width' bits starting at 'start' position."""
    mask = (1 << width) - 1
    return (n >> start) & mask
 
 
def pack_rgb565(r: int, g: int, b: int) -> int:
    """
    Pack RGB values into 16-bit RGB565 format.
    
    Args:
        r: Red (0-31, 5 bits)
        g: Green (0-63, 6 bits)
        b: Blue (0-31, 5 bits)
    """
    return ((r & 0x1F) << 11) | ((g & 0x3F) << 5) | (b & 0x1F)
 
 
def unpack_rgb565(rgb565: int) -> tuple:
    """
    Unpack 16-bit RGB565 color into R, G, B components.
    
    Returns:
        Tuple of (red, green, blue)
    """
    r = extract_bits(rgb565, 11, 5)  # Bits 11-15
    g = extract_bits(rgb565, 5, 6)   # Bits 5-10
    b = extract_bits(rgb565, 0, 5)   # Bits 0-4
    return (r, g, b)
 
 
def rgb565_to_rgb888(rgb565: int) -> tuple:
    """Convert RGB565 to RGB888 (standard 8-bit per channel)."""
    r, g, b = unpack_rgb565(rgb565)
    # Scale up: 5-bit (0-31) to 8-bit (0-255)
    r8 = (r * 255) // 31
    g8 = (g * 255) // 63
    b8 = (b * 255) // 31
    return (r8, g8, b8)
 
 
# Demonstration
print("=== RGB565 Color Format ===\n")
 
# Pack a color
red, green, blue = 31, 63, 31  # Max values = White
white = pack_rgb565(red, green, blue)
print(f"Pack RGB({red}, {green}, {blue}) = 0x{white:04X} ({white})")
print(f"Binary: {format(white, '016b')}")
print()
 
# Unpack it
r, g, b = unpack_rgb565(white)
print(f"Unpack 0x{white:04X} = RGB({r}, {g}, {b})")
print()
 
# Convert some colors
test_colors = [
    (31, 0, 0, "Red"),
    (0, 63, 0, "Green"),
    (0, 0, 31, "Blue"),
    (31, 63, 31, "White"),
    (0, 0, 0, "Black"),
    (15, 31, 15, "Gray"),
]
 
print("Color conversions:")
print("RGB565   | Packed     | Binary            | RGB888")
print("-" * 65)
for r, g, b, name in test_colors:
    packed = pack_rgb565(r, g, b)
    r8, g8, b8 = rgb565_to_rgb888(packed)
    print(f"{name:8} | 0x{packed:04X}     | {format(packed, '016b')} | ({r8:3}, {g8:3}, {b8:3})")
 
 
print()
print("=== TCP Flags Example ===\n")
 
# TCP flags
TCP_FIN = 1 << 0  # 0x01
TCP_SYN = 1 << 1  # 0x02
TCP_RST = 1 << 2  # 0x04
TCP_PSH = 1 << 3  # 0x08
TCP_ACK = 1 << 4  # 0x10
TCP_URG = 1 << 5  # 0x20
 
def parse_tcp_flags(flags: int) -> dict:
    """Parse TCP flags byte into individual flags."""
    return {
        'FIN': bool(flags & TCP_FIN),
        'SYN': bool(flags & TCP_SYN),
        'RST': bool(flags & TCP_RST),
        'PSH': bool(flags & TCP_PSH),
        'ACK': bool(flags & TCP_ACK),
        'URG': bool(flags & TCP_URG),
    }
 
# SYN-ACK packet
syn_ack = TCP_SYN | TCP_ACK  # 0x12
print(f"SYN-ACK flags: 0x{syn_ack:02X} ({format(syn_ack, '06b')})")
print(f"Parsed: {parse_tcp_flags(syn_ack)}")

Edge Cases and Best Practices

When working with bit positions, several edge cases and best practices are worth noting:

Watch Out For

•Bit width limits — For 32-bit integers, positions 0-31 are valid. Position 32+ may give unexpected results (undefined in C/C++, wrapped in some languages).
•Signed integers — Right-shifting signed negative numbers may be arithmetic (preserves sign) or logical (fills with zeros) depending on the language. Use unsigned integers when possible.
•JavaScript 32-bit limit — JavaScript bitwise operators work on 32-bit integers. For larger values, use BigInt.
•Off-by-one errors — Remember that positions are 0-indexed. Bit 0 is the rightmost bit, not bit 1.
•Endianness — When parsing multi-byte data from files/networks, consider byte order (big-endian vs. little-endian).

edge_cases.py
Python
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
# Edge cases demonstration
 
print("=== Edge Cases ===\n")
 
# 1. Check valid bit range
def is_bit_set_safe(n: int, k: int, bit_width: int = 32) -> bool:
    """Safe bit check with bounds validation."""
    if k < 0 or k >= bit_width:
        raise ValueError(f"Bit position {k} out of range [0, {bit_width - 1}]")
    return (n & (1 << k)) != 0
 
# 2. Negative numbers and right shift
print("Right shift behavior with negative numbers:")
n = -1  # All bits set in two's complement
print(f"n = {n} (binary: all 1s in two's complement)")
for k in range(4):
    # In Python, >> is always arithmetic (fills with sign bit)
    result = (n >> k) & 1
    print(f"  Bit {k}: {result}")
 
print()
 
# 3. Demonstrate large shift
print("Large shift values:")
n = 5
for k in [0, 2, 31, 32, 64]:
    try:
        # In Python, this works for any k (Python has arbitrary precision)
        result = n & (1 << k)
        print(f"  5 & (1 << {k:2}) = {result}")
    except Exception as e:
        print(f"  5 & (1 << {k:2}) = Error: {e}")
 
print()
 
# 4. Best practice: Define constants for common bit widths
class BitWidth:
    BYTE = 8
    SHORT = 16
    INT = 32
    LONG = 64
 
def get_bit_safe(n: int, k: int, width: int = BitWidth.INT) -> int:
    """Get bit value with explicit width checking."""
    assert 0 <= k < width, f"Position {k} invalid for {width}-bit integer"
    return (n >> k) & 1
 
# 5. Useful utility: get binary string with grouping
def format_binary(n: int, width: int = 8, group: int = 4) -> str:
    """Format number as binary with space-separated groups."""
    bits = format(n & ((1 << width) - 1), f'0{width}b')
    groups = [bits[i:i+group] for i in range(0, len(bits), group)]
    return ' '.join(groups)
 
print("Formatted binary:")
for n in [0, 1, 15, 255, 0xABCD]:
    print(f"  {n:5} = {format_binary(n, 16)}")

Language-Specific Behavior

Summary and Key Takeaways

We've learned to work with bits at arbitrary positions—a fundamental skill for systems programming, protocol implementation, and low-level optimization. Let's consolidate the key insights:

Key Takeaways

•Position mask: 1 << k — Creates a mask with a single 1 at position k, value = 2^k.
•Check bit: (n & (1 << k)) != 0 — Tests if bit k is set.
•Get bit value: (n >> k) & 1 — Extracts the 0 or 1 value at position k.
•Extract field: (n >> start) & ((1 << width) - 1) — Extracts multi-bit fields.
•Permission systems — Bit flags enable efficient, elegant boolean flag management.
•Protocol parsing — Essential for working with binary data formats and network protocols.

What's Next:

Page Complete

4 / 5