Checking, Setting, Clearing, Toggling Bits

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

// Set bit i to a specific value (0 or 1)
function setBitTo(n: number, i: number, value: 0 | 1): number {
    // Clear the bit, then OR in the new value
    return (n & ~(1 << i)) | (value << i);
}
 
// Alternative: using conditional
function setBitToAlt(n: number, i: number, value: boolean): number {
    return value ? (n | (1 << i)) : (n & ~(1 << i));
}
 
// Demonstration
let n = 0b10101010;
console.log(`Original:        ${n.toString(2).padStart(8, '0')}`);
console.log(`Set bit 2 to 1:  ${setBitTo(n, 2, 1).toString(2).padStart(8, '0')}`);
console.log(`Set bit 2 to 0:  ${setBitTo(n, 2, 0).toString(2).padStart(8, '0')}`);
console.log(`Set bit 3 to 0:  ${setBitTo(n, 3, 0).toString(2).padStart(8, '0')}`);
console.log(`Set bit 3 to 1:  ${setBitTo(n, 3, 1).toString(2).padStart(8, '0')}`);
 
// Set bit based on external condition
function updateBitFromCondition(n: number, i: number, condition: boolean): number {
    return setBitTo(n, i, condition ? 1 : 0);
}
 
// Example: Set bit 0 if array is non-empty
const arr = [1, 2, 3];
let flags = 0;
flags = updateBitFromCondition(flags, 0, arr.length > 0);
console.log(`\nFlags after array check: ${flags.toString(2)}`);
 
// Branchless conditional set using arithmetic
function setBitIf(n: number, i: number, condition: boolean): number {
    // -condition converts true to -1 (all 1s) and false to 0
    const condMask = condition ? -1 : 0;  // Or: -(+condition)
    const bitMask = 1 << i;
    return n | (bitMask & condMask);
}
 
console.log(`\nBranchless set bit 5 if true:  ${setBitIf(0, 5, true).toString(2)}`);
console.log(`Branchless set bit 5 if false: ${setBitIf(0, 5, false).toString(2)}`);
 
---python
# Set bit i to a specific value (0 or 1)
def set_bit_to(n: int, i: int, value: int) -> int:
    """Set bit i to value (0 or 1)."""
    # Clear the bit, then OR in the new value
    return (n & ~(1 << i)) | ((value & 1) << i)
 
# Alternative: using conditional
def set_bit_to_alt(n: int, i: int, value: bool) -> int:
    return (n | (1 << i)) if value else (n & ~(1 << i))
 
# Demonstration
n = 0b10101010
print(f"Original:        {bin(n)[2:].zfill(8)}")
print(f"Set bit 2 to 1:  {bin(set_bit_to(n, 2, 1))[2:].zfill(8)}")
print(f"Set bit 2 to 0:  {bin(set_bit_to(n, 2, 0))[2:].zfill(8)}")
print(f"Set bit 3 to 0:  {bin(set_bit_to(n, 3, 0))[2:].zfill(8)}")
print(f"Set bit 3 to 1:  {bin(set_bit_to(n, 3, 1))[2:].zfill(8)}")
 
# Set bit based on external condition
def update_bit_from_condition(n: int, i: int, condition: bool) -> int:
    return set_bit_to(n, i, 1 if condition else 0)
 
# Example: Set bit 0 if list is non-empty
arr = [1, 2, 3]
flags = 0
flags = update_bit_from_condition(flags, 0, len(arr) > 0)
print(f"\nFlags after array check: {bin(flags)}")
 
# Branchless conditional set (Python style)
def set_bit_if(n: int, i: int, condition: bool) -> int:
    """Set bit if condition is true, using branchless approach."""
    cond_mask = -int(condition)  # -1 if True, 0 if False
    bit_mask = 1 << i
    return n | (bit_mask & cond_mask)
 
print(f"\nBranchless set bit 5 if True:  {bin(set_bit_if(0, 5, True))}")
print(f"Branchless set bit 5 if False: {bin(set_bit_if(0, 5, False))}")

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

// Copy bit from position src to position dst
 
function copyBit(n: number, src: number, dst: number): number {
    // Extract source bit value (0 or 1)
    const bitValue = (n >> src) & 1;
    
    // Clear destination bit
    const cleared = n & ~(1 << dst);
    
    // Set destination to source value
    return cleared | (bitValue << dst);
}
 
// Demonstration
let n = 0b10101010;
console.log(`Original:          ${n.toString(2).padStart(8, '0')}`);
console.log(`Bit 1 = ${(n >> 1) & 1}, Bit 3 = ${(n >> 3) & 1}`);
 
const copied = copyBit(n, 1, 3);  // Copy bit 1 (which is 1) to position 3
console.log(`Copy bit 1 to 3:   ${copied.toString(2).padStart(8, '0')}`);
console.log(`Now bit 3 = ${(copied >> 3) & 1}`);
 
// Copy bit between two different numbers
function copyBitBetween(source: number, srcPos: number, 
                         dest: number, dstPos: number): number {
    const bitValue = (source >> srcPos) & 1;
    const cleared = dest & ~(1 << dstPos);
    return cleared | (bitValue << dstPos);
}
 
// Example: Copy bit 2 from 'a' to bit 5 in 'b'
const a = 0b00000100;  // bit 2 is set
const b = 0b00000000;  // all zeros
const result = copyBitBetween(a, 2, b, 5);
console.log(`\nCopy bit 2 from a to bit 5 in b:`);
console.log(`a = ${a.toString(2).padStart(8, '0')}`);
console.log(`b = ${b.toString(2).padStart(8, '0')}`);
console.log(`result = ${result.toString(2).padStart(8, '0')}`);  // bit 5 set
 
---python
# Copy bit from position src to position dst
 
def copy_bit(n: int, src: int, dst: int) -> int:
    """Copy bit from position src to position dst in n."""
    # Extract source bit value (0 or 1)
    bit_value = (n >> src) & 1
    
    # Clear destination bit
    cleared = n & ~(1 << dst)
    
    # Set destination to source value
    return cleared | (bit_value << dst)
 
# Demonstration
n = 0b10101010
print(f"Original:          {bin(n)[2:].zfill(8)}")
print(f"Bit 1 = {(n >> 1) & 1}, Bit 3 = {(n >> 3) & 1}")
 
copied = copy_bit(n, 1, 3)  # Copy bit 1 (which is 1) to position 3
print(f"Copy bit 1 to 3:   {bin(copied)[2:].zfill(8)}")
print(f"Now bit 3 = {(copied >> 3) & 1}")
 
# Copy bit between two different numbers
def copy_bit_between(source: int, src_pos: int, 
                     dest: int, dst_pos: int) -> int:
    """Copy a bit from source to dest at different positions."""
    bit_value = (source >> src_pos) & 1
    cleared = dest & ~(1 << dst_pos)
    return cleared | (bit_value << dst_pos)
 
# Example
a = 0b00000100  # bit 2 is set
b = 0b00000000  # all zeros
result = copy_bit_between(a, 2, b, 5)
print(f"\nCopy bit 2 from a to bit 5 in b:")
print(f"a = {bin(a)[2:].zfill(8)}")
print(f"b = {bin(b)[2:].zfill(8)}")
print(f"result = {bin(result)[2:].zfill(8)}")  # bit 5 set

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

// Swap bits at positions i and j
 
// Method 1: Using copy operations (straightforward)
function swapBitsSimple(n: number, i: number, j: number): number {
    const bitI = (n >> i) & 1;
    const bitJ = (n >> j) & 1;
    
    // Clear both positions
    let result = n & ~((1 << i) | (1 << j));
    
    // Set i to bitJ value and j to bitI value
    result |= (bitJ << i) | (bitI << j);
    
    return result;
}
 
// Method 2: Using XOR (elegant, O(1) without extra variables)
function swapBitsXor(n: number, i: number, j: number): number {
    // Only swap if bits are different
    const bitI = (n >> i) & 1;
    const bitJ = (n >> j) & 1;
    
    if (bitI !== bitJ) {
        // XOR with mask that has 1s at both positions flips both
        n ^= (1 << i) | (1 << j);
    }
    
    return n;
}
 
// Method 3: Branchless XOR swap
function swapBitsBranchless(n: number, i: number, j: number): number {
    // XOR of the two bits: 1 if different, 0 if same
    const xorBit = ((n >> i) ^ (n >> j)) & 1;
    
    // Create mask with xorBit at both positions
    const mask = (xorBit << i) | (xorBit << j);
    
    // XOR toggles both if they were different, does nothing if same
    return n ^ mask;
}
 
// Demonstration
function demo(method: (n: number, i: number, j: number) => number, name: string): void {
    console.log(`\n=== ${name} ===`);
    
    // Test case 1: Different bits
    let n = 0b10000001;  // bits 0 and 7 are different
    console.log(`Before: ${n.toString(2).padStart(8, '0')} (bit 0=1, bit 7=1)`);
    n = method(n, 1, 6);  // Swap bit 1 (0) with bit 6 (0) - same
    console.log(`Swap 1,6: ${n.toString(2).padStart(8, '0')} (same bits, no change)`);
    
    n = 0b01000010;  // bit 1 = 1, bit 6 = 1, others = 0
    console.log(`Before: ${n.toString(2).padStart(8, '0')} (bit 1=1, bit 6=1)`);
    n = method(n, 0, 7);  // Swap 0 (0) with 7 (0) - same
    console.log(`Swap 0,7: ${n.toString(2).padStart(8, '0')} (same 0s, no change)`);
    
    n = 0b10000010;  // bit 1 = 1, bit 7 = 1
    console.log(`Before: ${n.toString(2).padStart(8, '0')} (bit 1=1, bit 7=1, bit 0=0)`);
    n = method(n, 0, 1);  // Swap bit 0 (0) with bit 1 (1) - different!
    console.log(`Swap 0,1: ${n.toString(2).padStart(8, '0')} (swapped!)`);
}
 
demo(swapBitsSimple, "Simple Method");
demo(swapBitsXor, "XOR Method");
demo(swapBitsBranchless, "Branchless XOR Method");
 
---python
# Swap bits at positions i and j
 
# Method 1: Using copy operations (straightforward)
def swap_bits_simple(n: int, i: int, j: int) -> int:
    bit_i = (n >> i) & 1
    bit_j = (n >> j) & 1
    
    # Clear both positions
    result = n & ~((1 << i) | (1 << j))
    
    # Set i to bit_j value and j to bit_i value
    result |= (bit_j << i) | (bit_i << j)
    
    return result
 
# Method 2: Using XOR (elegant)
def swap_bits_xor(n: int, i: int, j: int) -> int:
    bit_i = (n >> i) & 1
    bit_j = (n >> j) & 1
    
    if bit_i != bit_j:
        # XOR with mask that has 1s at both positions
        n ^= (1 << i) | (1 << j)
    
    return n
 
# Method 3: Branchless XOR swap
def swap_bits_branchless(n: int, i: int, j: int) -> int:
    # XOR of the two bits: 1 if different, 0 if same
    xor_bit = ((n >> i) ^ (n >> j)) & 1
    
    # Create mask with xor_bit at both positions
    mask = (xor_bit << i) | (xor_bit << j)
    
    return n ^ mask
 
# Demonstration
def demo(method, name: str):
    print(f"\n=== {name} ===")
    
    n = 0b10000010  # bit 1 = 1, bit 7 = 1
    print(f"Before: {bin(n)[2:].zfill(8)} (bit 1=1, bit 7=1, bit 0=0)")
    result = method(n, 0, 1)  # Swap bit 0 (0) with bit 1 (1)
    print(f"Swap 0,1: {bin(result)[2:].zfill(8)} (swapped!)")
 
demo(swap_bits_simple, "Simple Method")
demo(swap_bits_xor, "XOR Method")
demo(swap_bits_branchless, "Branchless XOR Method")

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
131
132
133
134
135
136
137
138
139
140
141
142

// Generic multi-bit field operations
 
class BitField {
    constructor(
        public readonly position: number,  // Starting bit position (LSB of field)
        public readonly width: number       // Number of bits in field
    ) {}
    
    // Mask for this field (all 1s in the field position)
    get mask(): number {
        return ((1 << this.width) - 1) << this.position;
    }
    
    // Max value that fits in this field
    get maxValue(): number {
        return (1 << this.width) - 1;
    }
}
 
// Extract field value from n
function getField(n: number, field: BitField): number {
    return (n >> field.position) & ((1 << field.width) - 1);
}
 
// Set field to a new value (clearing old value first)
function setField(n: number, field: BitField, value: number): number {
    // Clamp value to field's max
    value = value & field.maxValue;
    
    // Clear the field, then set the new value
    return (n & ~field.mask) | (value << field.position);
}
 
// Clear field (set all bits in field to 0)
function clearField(n: number, field: BitField): number {
    return n & ~field.mask;
}
 
// Example: Packed date format
// Bits 0-4: Day (1-31, needs 5 bits)
// Bits 5-8: Month (1-12, needs 4 bits)
// Bits 9-15: Year offset from 2000 (0-127, needs 7 bits)
 
const DAY = new BitField(0, 5);
const MONTH = new BitField(5, 4);
const YEAR = new BitField(9, 7);
 
function packDate(year: number, month: number, day: number): number {
    let packed = 0;
    packed = setField(packed, YEAR, year - 2000);
    packed = setField(packed, MONTH, month);
    packed = setField(packed, DAY, day);
    return packed;
}
 
function unpackDate(packed: number): { year: number; month: number; day: number } {
    return {
        year: getField(packed, YEAR) + 2000,
        month: getField(packed, MONTH),
        day: getField(packed, DAY),
    };
}
 
// Demo
const packed = packDate(2024, 7, 15);
console.log(`Packed date: ${packed} (binary: ${packed.toString(2).padStart(16, '0')})`);
 
const unpacked = unpackDate(packed);
console.log(`Unpacked: ${unpacked.year}-${unpacked.month}-${unpacked.day}`);
 
// Modify just the month
const newPacked = setField(packed, MONTH, 12);
const newUnpacked = unpackDate(newPacked);
console.log(`After changing month to 12: ${newUnpacked.year}-${newUnpacked.month}-${newUnpacked.day}`);
 
---python
# Generic multi-bit field operations
 
from dataclasses import dataclass
 
@dataclass
class BitField:
    position: int  # Starting bit position (LSB of field)
    width: int     # Number of bits in field
    
    @property
    def mask(self) -> int:
        """Mask for this field (all 1s in the field position)."""
        return ((1 << self.width) - 1) << self.position
    
    @property
    def max_value(self) -> int:
        """Max value that fits in this field."""
        return (1 << self.width) - 1
 
def get_field(n: int, field: BitField) -> int:
    """Extract field value from n."""
    return (n >> field.position) & ((1 << field.width) - 1)
 
def set_field(n: int, field: BitField, value: int) -> int:
    """Set field to a new value (clearing old value first)."""
    value = value & field.max_value  # Clamp to max
    return (n & ~field.mask) | (value << field.position)
 
def clear_field(n: int, field: BitField) -> int:
    """Clear field (set all bits in field to 0)."""
    return n & ~field.mask
 
# Example: Packed date format
# Bits 0-4: Day (1-31, needs 5 bits)
# Bits 5-8: Month (1-12, needs 4 bits)
# Bits 9-15: Year offset from 2000 (0-127, needs 7 bits)
 
DAY = BitField(0, 5)
MONTH = BitField(5, 4)
YEAR = BitField(9, 7)
 
def pack_date(year: int, month: int, day: int) -> int:
    packed = 0
    packed = set_field(packed, YEAR, year - 2000)
    packed = set_field(packed, MONTH, month)
    packed = set_field(packed, DAY, day)
    return packed
 
def unpack_date(packed: int) -> dict:
    return {
        'year': get_field(packed, YEAR) + 2000,
        'month': get_field(packed, MONTH),
        'day': get_field(packed, DAY),
    }
 
# Demo
packed = pack_date(2024, 7, 15)
print(f"Packed date: {packed} (binary: {bin(packed)[2:].zfill(16)})")
 
unpacked = unpack_date(packed)
print(f"Unpacked: {unpacked['year']}-{unpacked['month']}-{unpacked['day']}")
 
# Modify just the month
new_packed = set_field(packed, MONTH, 12)
new_unpacked = unpack_date(new_packed)
print(f"After changing month to 12: {new_unpacked['year']}-{new_unpacked['month']}-{new_unpacked['day']}")

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

// Read-Modify-Write patterns with combined operations
 
// Pattern 1: Set a bit only if it's currently clear
function setIfClear(n: number, i: number): { result: number; wasSet: boolean } {
    const wasClear = ((n >> i) & 1) === 0;  // READ
    if (wasClear) {
        n = n | (1 << i);  // MODIFY + WRITE
    }
    return { result: n, wasSet: wasClear };
}
 
// Pattern 2: Clear a bit only if it's currently set
function clearIfSet(n: number, i: number): { result: number; wasCleared: boolean } {
    const wasSet = ((n >> i) & 1) === 1;  // READ
    if (wasSet) {
        n = n & ~(1 << i);  // MODIFY + WRITE
    }
    return { result: n, wasCleared: wasSet };
}
 
// Pattern 3: Toggle and return the new value
function toggleAndRead(n: number, i: number): { result: number; newValue: 0 | 1 } {
    const toggled = n ^ (1 << i);  // MODIFY + WRITE
    const newValue = ((toggled >> i) & 1) as 0 | 1;  // READ from result
    return { result: toggled, newValue };
}
 
// Pattern 4: Atomic-style compare and set (conceptual - not truly atomic in JS)
function compareAndSet(
    current: number, 
    i: number, 
    expectedValue: 0 | 1, 
    newValue: 0 | 1
): { result: number; success: boolean } {
    const actualValue = (current >> i) & 1;
    
    if (actualValue === expectedValue) {
        // Value matches expectation, safe to modify
        const result = (current & ~(1 << i)) | (newValue << i);
        return { result, success: true };
    }
    
    // Value doesn't match, no modification
    return { result: current, success: false };
}
 
// Demo: Permission escalation with tracking
console.log("=== Set-If-Clear Demo ===");
let perms = 0b00000101;  // READ and EXECUTE
console.log(`Initial perms: ${perms.toString(2).padStart(8, '0')}`);
 
const { result: perms2, wasSet: grantedWrite } = setIfClear(perms, 1);
console.log(`Try grant WRITE: success=${grantedWrite}, perms=${perms2.toString(2).padStart(8, '0')}`);
 
const { result: perms3, wasSet: grantedWriteAgain } = setIfClear(perms2, 1);
console.log(`Try grant WRITE again: success=${grantedWriteAgain}, perms=${perms3.toString(2).padStart(8, '0')}`);
 
// Demo: Toggle and track
console.log("\n=== Toggle-And-Read Demo ===");
let state = 0;
for (let i = 0; i < 4; i++) {
    const { result, newValue } = toggleAndRead(state, 0);
    state = result;
    console.log(`Toggle #${i + 1}: bit is now ${newValue}`);
}
 
---python
# Read-Modify-Write patterns with combined operations
 
from typing import Tuple
 
# Pattern 1: Set a bit only if it's currently clear
def set_if_clear(n: int, i: int) -> Tuple[int, bool]:
    """Set bit i only if it's currently 0. Returns (result, was_set)."""
    was_clear = ((n >> i) & 1) == 0  # READ
    if was_clear:
        n = n | (1 << i)  # MODIFY + WRITE
    return n, was_clear
 
# Pattern 2: Clear a bit only if it's currently set
def clear_if_set(n: int, i: int) -> Tuple[int, bool]:
    """Clear bit i only if it's currently 1. Returns (result, was_cleared)."""
    was_set = ((n >> i) & 1) == 1  # READ
    if was_set:
        n = n & ~(1 << i)  # MODIFY + WRITE
    return n, was_set
 
# Pattern 3: Toggle and return the new value
def toggle_and_read(n: int, i: int) -> Tuple[int, int]:
    """Toggle bit i and return (result, new_bit_value)."""
    toggled = n ^ (1 << i)  # MODIFY + WRITE
    new_value = (toggled >> i) & 1  # READ from result
    return toggled, new_value
 
# Pattern 4: Compare and set (conceptual)
def compare_and_set(current: int, i: int, 
                    expected: int, new_value: int) -> Tuple[int, bool]:
    """
    Set bit i to new_value only if current value matches expected.
    Returns (result, success).
    """
    actual = (current >> i) & 1
    
    if actual == expected:
        result = (current & ~(1 << i)) | ((new_value & 1) << i)
        return result, True
    
    return current, False
 
# Demo
print("=== Set-If-Clear Demo ===")
perms = 0b00000101  # READ and EXECUTE
print(f"Initial perms: {bin(perms)[2:].zfill(8)}")
 
perms, granted_write = set_if_clear(perms, 1)
print(f"Try grant WRITE: success={granted_write}, perms={bin(perms)[2:].zfill(8)}")
 
perms, granted_write_again = set_if_clear(perms, 1)
print(f"Try grant WRITE again: success={granted_write_again}, perms={bin(perms)[2:].zfill(8)}")
 
print("\n=== Toggle-And-Read Demo ===")
state = 0
for i in range(4):
    state, new_value = toggle_and_read(state, 0)
    print(f"Toggle #{i + 1}: bit is now {new_value}")

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260

/**
 * Complete Bit Manipulation Toolkit
 * All fundamental operations with consistent naming and documentation
 */
 
export class BitOps {
    // ==================== Single Bit Operations ====================
    
    /** Check if bit i is set (returns 0 or 1) */
    static getBit(n: number, i: number): number {
        return (n >> i) & 1;
    }
    
    /** Check if bit i is set (returns boolean) */
    static isBitSet(n: number, i: number): boolean {
        return ((n >> i) & 1) === 1;
    }
    
    /** Set bit i to 1 */
    static setBit(n: number, i: number): number {
        return n | (1 << i);
    }
    
    /** Clear bit i to 0 */
    static clearBit(n: number, i: number): number {
        return n & ~(1 << i);
    }
    
    /** Toggle bit i */
    static toggleBit(n: number, i: number): number {
        return n ^ (1 << i);
    }
    
    /** Set bit i to a specific value (0 or 1) */
    static setBitTo(n: number, i: number, value: number): number {
        return (n & ~(1 << i)) | ((value & 1) << i);
    }
    
    // ==================== Multi-Bit Operations ====================
    
    /** Set multiple bits using a mask */
    static setBits(n: number, mask: number): number {
        return n | mask;
    }
    
    /** Clear multiple bits using a mask */
    static clearBits(n: number, mask: number): number {
        return n & ~mask;
    }
    
    /** Toggle multiple bits using a mask */
    static toggleBits(n: number, mask: number): number {
        return n ^ mask;
    }
    
    // ==================== Range Operations ====================
    
    /** Create mask for bits from position low to high (inclusive) */
    static rangeMask(low: number, high: number): number {
        return ((1 << (high - low + 1)) - 1) << low;
    }
    
    /** Extract bits from position low to high */
    static getRange(n: number, low: number, high: number): number {
        return (n >> low) & ((1 << (high - low + 1)) - 1);
    }
    
    /** Clear bits from position low to high */
    static clearRange(n: number, low: number, high: number): number {
        return n & ~this.rangeMask(low, high);
    }
    
    /** Set bits from position low to high */
    static setRange(n: number, low: number, high: number): number {
        return n | this.rangeMask(low, high);
    }
    
    // ==================== Bit Position Operations ====================
    
    /** Copy bit from srcPos to dstPos */
    static copyBit(n: number, srcPos: number, dstPos: number): number {
        const bit = (n >> srcPos) & 1;
        return (n & ~(1 << dstPos)) | (bit << dstPos);
    }
    
    /** Swap bits at positions i and j */
    static swapBits(n: number, i: number, j: number): number {
        const xorBit = ((n >> i) ^ (n >> j)) & 1;
        return n ^ ((xorBit << i) | (xorBit << j));
    }
    
    // ==================== Utility Operations ====================
    
    /** Count set bits (popcount) */
    static countBits(n: number): number {
        let count = 0;
        while (n) {
            count += n & 1;
            n >>>= 1;
        }
        return count;
    }
    
    /** Get position of lowest set bit (0-indexed, -1 if no bits set) */
    static lowestSetBit(n: number): number {
        if (n === 0) return -1;
        let pos = 0;
        while ((n & 1) === 0) {
            n >>>= 1;
            pos++;
        }
        return pos;
    }
    
    /** Get the lowest set bit as a value (isolate rightmost 1) */
    static isolateLowestBit(n: number): number {
        return n & (-n);
    }
    
    /** Clear the lowest set bit */
    static clearLowestBit(n: number): number {
        return n & (n - 1);
    }
    
    /** Check if n is a power of two */
    static isPowerOfTwo(n: number): boolean {
        return n > 0 && (n & (n - 1)) === 0;
    }
    
    // ==================== Visualization ====================
    
    /** Get binary string representation */
    static toBinary(n: number, width: number = 8): string {
        return (n >>> 0).toString(2).padStart(width, '0');
    }
}
 
// Demo
console.log("=== BitOps Toolkit Demo ===\n");
 
const n = 0b10101010;
console.log(`n = ${BitOps.toBinary(n)}`);
console.log(`getBit(n, 3) = ${BitOps.getBit(n, 3)}`);
console.log(`setBit(n, 2) = ${BitOps.toBinary(BitOps.setBit(n, 2))}`);
console.log(`clearBit(n, 5) = ${BitOps.toBinary(BitOps.clearBit(n, 5))}`);
console.log(`toggleBit(n, 0) = ${BitOps.toBinary(BitOps.toggleBit(n, 0))}`);
console.log(`swapBits(n, 1, 4) = ${BitOps.toBinary(BitOps.swapBits(n, 1, 4))}`);
console.log(`countBits(n) = ${BitOps.countBits(n)}`);
console.log(`isPowerOfTwo(8) = ${BitOps.isPowerOfTwo(8)}`);
 
---python
"""
Complete Bit Manipulation Toolkit
All fundamental operations with consistent naming and documentation
"""
 
class BitOps:
    # ==================== Single Bit Operations ====================
    
    @staticmethod
    def get_bit(n: int, i: int) -> int:
        """Check if bit i is set (returns 0 or 1)."""
        return (n >> i) & 1
    
    @staticmethod
    def is_bit_set(n: int, i: int) -> bool:
        """Check if bit i is set (returns boolean)."""
        return ((n >> i) & 1) == 1
    
    @staticmethod
    def set_bit(n: int, i: int) -> int:
        """Set bit i to 1."""
        return n | (1 << i)
    
    @staticmethod
    def clear_bit(n: int, i: int) -> int:
        """Clear bit i to 0."""
        return n & ~(1 << i)
    
    @staticmethod
    def toggle_bit(n: int, i: int) -> int:
        """Toggle bit i."""
        return n ^ (1 << i)
    
    @staticmethod
    def set_bit_to(n: int, i: int, value: int) -> int:
        """Set bit i to a specific value (0 or 1)."""
        return (n & ~(1 << i)) | ((value & 1) << i)
    
    # ==================== Multi-Bit Operations ====================
    
    @staticmethod
    def set_bits(n: int, mask: int) -> int:
        """Set multiple bits using a mask."""
        return n | mask
    
    @staticmethod
    def clear_bits(n: int, mask: int) -> int:
        """Clear multiple bits using a mask."""
        return n & ~mask
    
    @staticmethod
    def toggle_bits(n: int, mask: int) -> int:
        """Toggle multiple bits using a mask."""
        return n ^ mask
    
    # ==================== Range Operations ====================
    
    @staticmethod
    def range_mask(low: int, high: int) -> int:
        """Create mask for bits from position low to high (inclusive)."""
        return ((1 << (high - low + 1)) - 1) << low
    
    @staticmethod
    def get_range(n: int, low: int, high: int) -> int:
        """Extract bits from position low to high."""
        return (n >> low) & ((1 << (high - low + 1)) - 1)
    
    # ==================== Utility Operations ====================
    
    @staticmethod
    def count_bits(n: int) -> int:
        """Count set bits (popcount)."""
        count = 0
        while n:
            count += n & 1
            n >>= 1
        return count
    
    @staticmethod
    def isolate_lowest_bit(n: int) -> int:
        """Get the lowest set bit as a value."""
        return n & (-n)
    
    @staticmethod
    def clear_lowest_bit(n: int) -> int:
        """Clear the lowest set bit."""
        return n & (n - 1)
    
    @staticmethod
    def is_power_of_two(n: int) -> bool:
        """Check if n is a power of two."""
        return n > 0 and (n & (n - 1)) == 0
    
    @staticmethod
    def to_binary(n: int, width: int = 8) -> str:
        """Get binary string representation."""
        return bin(n & ((1 << width) - 1))[2:].zfill(width)
 
# Demo
print("=== BitOps Toolkit Demo ===\n")
 
n = 0b10101010
print(f"n = {BitOps.to_binary(n)}")
print(f"get_bit(n, 3) = {BitOps.get_bit(n, 3)}")
print(f"set_bit(n, 2) = {BitOps.to_binary(BitOps.set_bit(n, 2))}")
print(f"clear_bit(n, 5) = {BitOps.to_binary(BitOps.clear_bit(n, 5))}")
print(f"toggle_bit(n, 0) = {BitOps.to_binary(BitOps.toggle_bit(n, 0))}")
print(f"count_bits(n) = {BitOps.count_bits(n)}")
print(f"is_power_of_two(8) = {BitOps.is_power_of_two(8)}")

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

/**
 * Compact Task Scheduler using Bit Manipulation
 * 
 * Each task is represented by a position (0-31).
 * We use multiple bitmasks to track different aspects:
 * - completed: which tasks are done
 * - running: which tasks are currently executing
 * - blocked: which tasks are waiting for dependencies
 * - ready: which tasks can be executed
 */
 
class BitTaskScheduler {
    private completed = 0;
    private running = 0;
    private blocked = 0;
    
    // Dependencies: dependencies[i] is a mask of tasks that task i depends on
    private dependencies: number[] = new Array(32).fill(0);
    
    // Add a dependency: task depends on prerequisite
    addDependency(task: number, prerequisite: number): void {
        this.dependencies[task] |= (1 << prerequisite);  // SET dependency bit
        this.blocked |= (1 << task);  // Mark as blocked
    }
    
    // Get tasks that are ready to run
    getReadyTasks(): number {
        // Ready = not completed AND not running AND not blocked
        return ~this.completed & ~this.running & ~this.blocked;
    }
    
    // Start a task
    startTask(task: number): boolean {
        const mask = 1 << task;
        
        // Check if task can be started
        if (!(this.getReadyTasks() & mask)) {
            return false;  // Not ready
        }
        
        this.running |= mask;  // SET running bit
        return true;
    }
    
    // Complete a task
    completeTask(task: number): void {
        const mask = 1 << task;
        
        // Clear running, set completed
        this.running &= ~mask;  // CLEAR running
        this.completed |= mask;  // SET completed
        
        // Update blocked status for dependent tasks
        for (let i = 0; i < 32; i++) {
            if (this.dependencies[i] & mask) {
                // This task was waiting for the completed one
                this.dependencies[i] &= ~mask;  // CLEAR dependency
                
                // If all dependencies cleared, unblock the task
                if (this.dependencies[i] === 0) {
                    this.blocked &= ~(1 << i);  // CLEAR blocked
                }
            }
        }
    }
    
    // Check if all tasks in mask are completed
    areTasksCompleted(taskMask: number): boolean {
        return (this.completed & taskMask) === taskMask;
    }
    
    // Check if any task in mask is running
    isAnyTaskRunning(taskMask: number): boolean {
        return (this.running & taskMask) !== 0;
    }
    
    // Get status for display
    getStatus(): string {
        return `Completed: ${this.completed.toString(2).padStart(8, '0')}
Running:   ${this.running.toString(2).padStart(8, '0')}
Blocked:   ${this.blocked.toString(2).padStart(8, '0')}
Ready:     ${(this.getReadyTasks() & 0xFF).toString(2).padStart(8, '0')}`;
    }
}
 
// Demo: Build pipeline with dependencies
// Task 0: Download source
// Task 1: Install dependencies (needs 0)
// Task 2: Run tests (needs 1)
// Task 3: Build app (needs 1)
// Task 4: Deploy (needs 2, 3)
 
const scheduler = new BitTaskScheduler();
 
// Set up dependencies
scheduler.addDependency(1, 0);  // Install needs Download
scheduler.addDependency(2, 1);  // Tests needs Install
scheduler.addDependency(3, 1);  // Build needs Install
scheduler.addDependency(4, 2);  // Deploy needs Tests
scheduler.addDependency(4, 3);  // Deploy needs Build
 
console.log("=== Initial State ===");
console.log(scheduler.getStatus());
 
console.log("\n=== Start & Complete Task 0 (Download) ===");
scheduler.startTask(0);
scheduler.completeTask(0);
console.log(scheduler.getStatus());
 
console.log("\n=== Start & Complete Task 1 (Install) ===");
scheduler.startTask(1);
scheduler.completeTask(1);
console.log(scheduler.getStatus());
 
console.log("\n=== Start Tasks 2 and 3 in parallel ===");
scheduler.startTask(2);
scheduler.startTask(3);
console.log(scheduler.getStatus());
 
console.log("\n=== Complete Tasks 2 and 3 ===");
scheduler.completeTask(2);
scheduler.completeTask(3);
console.log(scheduler.getStatus());
 
console.log("\n=== Start & Complete Task 4 (Deploy) ===");
scheduler.startTask(4);
scheduler.completeTask(4);
console.log(scheduler.getStatus());