Skip to content

Bitwise Operations Guide

This guide provides a comprehensive introduction to bitwise operations in Harneet, covering concepts, practical applications, and performance considerations.

Understanding Binary Representation

Before diving into bitwise operations, it's essential to understand how integers are represented in binary.

Binary Basics

Binary Basics
1
2
3
4
5
// Decimal to Binary Examples
12 → 1100 (binary)
10 → 1010 (binary)
 5 → 0101 (binary)
 0 → 0000 (binary)

Bit Positions

Bit Positions
1
2
3
Bit Position:  7  6  5  4  3  2  1  0
Binary:        1  1  0  0  1  0  1  0
Decimal Value: 128+64+0+0+8+0+2+0 = 202

Bitwise Operators

Bitwise AND (&)

The AND operator returns 1 only when both bits are 1.

Bitwise AND
1
2
3
4
5
6
7
package main
import fmt
var a int = 12  // 1100
var b int = 10  // 1010
var result int = a & b  // 1000 = 8

fmt.Printf("%d & %d = %d\n", a, b, result)

Truth Table: 

1
2
3
4
5
6
A | B | A & B
--|---|------
0 | 0 |   0
0 | 1 |   0
1 | 0 |   0
1 | 1 |   1

Common Uses: - Masking bits - Checking if specific bits are set - Clearing bits

Bitwise OR (|)

The OR operator returns 1 when at least one bit is 1.

Bitwise OR
1
2
3
4
5
6
7
package main
import fmt
var a int = 12  // 1100
var b int = 10  // 1010
var result int = a | b  // 1110 = 14

fmt.Printf("%d | %d = %d\n", a, b, result)

Truth Table: 

1
2
3
4
5
6
A | B | A | B
--|---|------
0 | 0 |   0
0 | 1 |   1
1 | 0 |   1
1 | 1 |   1

Common Uses: - Setting bits - Combining flags - Creating bitmasks

Bitwise XOR (^)

The XOR operator returns 1 when bits are different.

Bitwise XOR
1
2
3
4
5
6
7
package main
import fmt
var a int = 12  // 1100
var b int = 10  // 1010
var result int = a ^ b  // 0110 = 6

fmt.Printf("%d ^ %d = %d\n", a, b, result)

Truth Table: 

1
2
3
4
5
6
A | B | A ^ B
--|---|------
0 | 0 |   0
0 | 1 |   1
1 | 0 |   1
1 | 1 |   0

Common Uses: - Toggling bits - Simple encryption - Swapping variables without temporary storage

Bitwise NOT (~)

The NOT operator inverts all bits (1 becomes 0, 0 becomes 1).

Bitwise NOT
1
2
3
4
5
6
package main
import fmt
var a int = 5   // 0101
var result int = ~a  // 1010... (depends on integer size)

fmt.Printf("~%d = %d\n", a, result)

Note: The result depends on the integer size and sign representation.

Left Shift (<<)

Shifts bits to the left, filling with zeros from the right.

Left Shift
1
2
3
4
5
6
package main
import fmt
var a int = 5    // 0101
var result int = a << 2  // 010100 = 20

fmt.Printf("%d << 2 = %d\n", a, result)

Effect: Equivalent to multiplying by 2^n where n is the shift amount.

Right Shift (>>)

Shifts bits to the right, discarding bits that fall off.

Right Shift
1
2
3
4
5
6
package main
import fmt
var a int = 20   // 10100
var result int = a >> 2  // 101 = 5

fmt.Printf("%d >> 2 = %d\n", a, result)

Effect: Equivalent to dividing by 2^n where n is the shift amount (for positive numbers).

Practical Applications

1. Flag Management

Bitwise operations are perfect for managing multiple boolean flags efficiently.

Flag Management
 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
package main
import fmt
// Define flag constants
var READ_FLAG int = 1   // 001
var WRITE_FLAG int = 2  // 010
var EXEC_FLAG int = 4   // 100

// Set permissions
var permissions int = READ_FLAG | WRITE_FLAG
fmt.Printf("Permissions: %d\n", permissions)  // 3

// Check if has read permission
if (permissions & READ_FLAG) != 0 {
    fmt.Println("Has read permission")
}

// Add execute permission
permissions |= EXEC_FLAG
fmt.Printf("After adding execute: %d\n", permissions)  // 7

// Remove write permission
permissions &= ~WRITE_FLAG
fmt.Printf("After removing write: %d\n", permissions)  // 5

// Toggle read permission
permissions ^= READ_FLAG
fmt.Printf("After toggling read: %d\n", permissions)  // 4

2. Bit Manipulation Tricks

Check if Number is Even/Odd

Even/Odd Check
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
package main
import fmt
function isEven(n int) bool {
    return (n & 1) == 0
}

var num int = 42
if isEven(num) {
    fmt.Printf("%d is even\n", num)
}

Check if Number is Power of 2

Power of Two Check
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
package main
import fmt
function isPowerOfTwo(n int) bool {
    return n > 0 and (n & (n - 1)) == 0
}

var numbers = [1, 2, 3, 4, 8, 15, 16]
for var i = 0; i < len(numbers); i = i + 1 {
    var num int = numbers[i]
    fmt.Printf("%d is power of 2: %t\n", num, isPowerOfTwo(num))
}

Swap Two Numbers Without Temporary Variable

Swap Without Temp
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
package main
import fmt
var a int = 25
var b int = 17
fmt.Printf("Before: a=%d, b=%d\n", a, b)

a ^= b
b ^= a
a ^= b

fmt.Printf("After: a=%d, b=%d\n", a, b)

Count Set Bits (Population Count)

Count Set Bits
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package main
import fmt
function countSetBits(n int) int {
    var count int = 0
    for n > 0 {
        count += n & 1
        n >>= 1
    }
    return count
}

// Optimized version (Brian Kernighan's algorithm)
function countSetBitsFast(n int) int {
    var count int = 0
    for n > 0 {
        n &= n - 1  // Clear the lowest set bit
        count = count + 1
    }
    return count
}

var num int = 42  // 101010 in binary
fmt.Printf("Set bits in %d: %d\n", num, countSetBits(num))

3. Performance Optimizations

Fast Multiplication/Division by Powers of 2

Fast Multiply/Divide by 2^n
1
2
3
4
5
6
7
8
9
// Instead of: result = value * 8
var result int = value << 3  // Faster

// Instead of: result = value / 4
var result2 int = value >> 2  // Faster (for positive numbers)

// Modulo with powers of 2
// Instead of: remainder = value % 8
var remainder int = value & 7  // Faster (8-1 = 7)

Absolute Value Without Branching

Absolute Value Without Branching
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
package main
import fmt
function abs(n int) int {
    var mask int = n >> 31  // Arithmetic right shift
    return (n ^ mask) - mask
}

var values = [-5, -1, 0, 1, 5]
for var i = 0; i < len(values); i = i + 1 {
    var val int = values[i]
    fmt.Printf("abs(%d) = %d\n", val, abs(val))
}

4. Bit Masking and Extraction

Extract Specific Bits

Extract Specific Bits
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
package main
import fmt
// Extract bits 2-4 from a number
function extractBits(value int, start int, length int) int {
    var mask int = (1 << length) - 1  // Create mask with 'length' ones
    return (value >> start) & mask
}

var value int = 0b11010110  // 214 in decimal
var extracted int = extractBits(value, 2, 3)  // Extract 3 bits starting at position 2
fmt.Printf("Extracted bits: %d\n", extracted)  // Should be 5 (101)

Set Specific Bits

Set/Clear/Toggle Bits
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
package main
import fmt
function setBit(value int, position int) int {
    return value | (1 << position)
}

function clearBit(value int, position int) int {
    return value & ~(1 << position)
}

function toggleBit(value int, position int) int {
    return value ^ (1 << position)
}

var value int = 0b10100000  // 160
fmt.Printf("Original: %d\n", value)
fmt.Printf("Set bit 2: %d\n", setBit(value, 2))      // 164
fmt.Printf("Clear bit 5: %d\n", clearBit(value, 5))  // 128
fmt.Printf("Toggle bit 3: %d\n", toggleBit(value, 3)) // 168

5. Cryptographic Applications

Simple XOR Cipher

Simple XOR Cipher
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
package main
import fmt
function xorEncrypt(data int, key int) int {
    return data ^ key
}

function xorDecrypt(encrypted int, key int) int {
    return encrypted ^ key  // XOR is its own inverse
}

var message int = 42
var key int = 123
var encrypted int = xorEncrypt(message, key)
var decrypted int = xorDecrypt(encrypted, key)

fmt.Printf("Original: %d\n", message)
fmt.Printf("Encrypted: %d\n", encrypted)
fmt.Printf("Decrypted: %d\n", decrypted)

6. Data Structure Optimizations

Bit Set Implementation

Bit Set Implementation
 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
package main
import fmt
// Simple bit set for numbers 0-63
var bitSet int = 0

// Add number to set
function addToSet(set int, num int) int {
    return set | (1 << num)
}

// Remove number from set
function removeFromSet(set int, num int) int {
    return set & ~(1 << num)
}

// Check if number is in set
function isInSet(set int, num int) bool {
    return (set & (1 << num)) != 0
}

// Example usage
bitSet = addToSet(bitSet, 5)
bitSet = addToSet(bitSet, 10)
bitSet = addToSet(bitSet, 15)

fmt.Printf("Is 5 in set: %t\n", isInSet(bitSet, 5))   // true
fmt.Printf("Is 7 in set: %t\n", isInSet(bitSet, 7))   // false

Performance Considerations

When to Use Bitwise Operations

Good Use Cases: - Flag management - Bit manipulation algorithms - Performance-critical code - Low-level system programming - Cryptographic operations - Data compression

Avoid When: - Code readability is more important than performance - Working with non-integer types - Complex logic that's clearer with regular operators

Performance Comparison

Performance Comparison
1
2
3
4
5
6
7
8
9
// Fast: Bitwise operations
var isEven bool = (n & 1) == 0
var doubled int = n << 1
var halved int = n >> 1

// Slower: Regular operations
var isEven2 bool = (n % 2) == 0
var doubled2 int = n * 2
var halved2 int = n / 2

Memory Efficiency

Bitwise operations can significantly reduce memory usage:

Memory Efficiency
1
2
3
4
5
6
7
8
9
// Instead of 8 boolean variables (8 bytes)
var flag1 bool = true
var flag2 bool = false
// ... 6 more flags

// Use a single integer (4 or 8 bytes)
var flags int = 0
flags |= 1 << 0  // Set flag1
flags &= ~(1 << 1)  // Clear flag2

Common Pitfalls and Best Practices

1. Shift Amount Validation

Shift Amount Validation
1
2
3
4
5
6
7
// Always validate shift amounts
function safeLeftShift(value int, amount int) int {
    if amount < 0 or amount >= 64 {
        return 0  // or handle error appropriately
    }
    return value << amount
}

2. Sign Extension with Right Shift

Sign Extension with Right Shift
1
2
3
// Be aware of sign extension with negative numbers
var negative int = -8  // 11111000 (in 8-bit representation)
var shifted int = negative >> 1  // May be -4 (11111100) due to sign extension

3. Operator Precedence

Operator Precedence
1
2
3
4
// Use parentheses for clarity
var result bool = (a & mask) != 0  // Clear intent
// vs
var result2 int = a & mask != 0   // Confusing due to precedence

4. Portability Considerations

Portability Considerations
1
2
3
// Be careful with integer sizes across platforms
// Use specific types when bit layout matters
var flags uint32 = 0  // Explicit 32-bit integer

Advanced Techniques

Bit Reversal

Bit Reversal
1
2
3
4
5
6
7
8
function reverseBits(n int) int {
    var result int = 0
    for var i = 0; i < 32; i = i + 1 {
        result = (result << 1) | (n & 1)
        n >>= 1
    }
    return result
}

Gray Code Conversion

Gray Code Conversion
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function binaryToGray(n int) int {
    return n ^ (n >> 1)
}

function grayToBinary(n int) int {
    var result int = n
    for n > 0 {
        n >>= 1
        result ^= n
    }
    return result
}

Next Power of 2

Next Power of Two
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function nextPowerOfTwo(n int) int {
    n--
    n |= n >> 1
    n |= n >> 2
    n |= n >> 4
    n |= n >> 8
    n |= n >> 16
    n = n + 1
    return n
}

Conclusion

Bitwise operations in Harneet provide powerful tools for: - Efficient flag management - Performance optimization - Low-level programming - Algorithmic problem solving - Memory-efficient data structures

Master these operations to write more efficient and elegant code, especially in systems programming and performance-critical applications. Remember to balance performance gains with code readability and maintainability.