Bitwise Tricks

Introduction

Bitwise operations are powerful tools in a programmer's toolkit that operate directly on the binary representation of data. While they may seem complex initially, mastering bitwise tricks can lead to more efficient code, elegant solutions to complex problems, and a deeper understanding of how computers work at a low level.

This guide explores common bitwise tricks that are useful in everyday programming scenarios. These techniques can help optimize your code, reduce computational complexity, and solve certain problems more efficiently than traditional approaches.

Why Learn Bitwise Tricks?

Bitwise operations have several advantages:

1. Performance: Bitwise operations are typically faster than arithmetic operations
2. Memory efficiency: They can store multiple boolean values in a single integer
3. Elegance: Some problems have remarkably concise solutions using bitwise techniques
4. System programming: Essential for low-level programming tasks like device drivers

Common Bitwise Operators

Before diving into the tricks, let's review the basic bitwise operators:

Operator	Name	Description
&	AND	Sets each bit to 1 if both bits are 1
|	OR	Sets each bit to 1 if at least one bit is 1
^	XOR	Sets each bit to 1 if only one bit is 1
~	NOT	Inverts all bits
<<	Left shift	Shifts bits to the left (multiplication by 2)
>>	Right shift	Shifts bits to the right (division by 2)

Basic Bitwise Tricks

1. Check if a number is even or odd

java

// Even numbers have their least significant bit as 0
boolean isEven = (num & 1) == 0;

// Example:
int num = 42;
if ((num & 1) == 0) {
    System.out.println(num + " is even");  // Output: 42 is even
} else {
    System.out.println(num + " is odd");
}

Explanation: The & operator with 1 checks the least significant bit. If it's 0, the number is even; if it's 1, the number is odd.

2. Multiply or divide by powers of 2

java

// Multiply by 2^n (left shift)
int multiplyByTwo = num << 1;     // num * 2
int multiplyByFour = num << 2;    // num * 4
int multiplyByEight = num << 3;   // num * 8

// Divide by 2^n (right shift)
int divideByTwo = num >> 1;       // num / 2
int divideByFour = num >> 2;      // num / 4
int divideByEight = num >> 3;     // num / 8

// Example:
int value = 10;
System.out.println(value + " * 4 = " + (value << 2));  // Output: 10 * 4 = 40
System.out.println(value + " / 2 = " + (value >> 1));  // Output: 10 / 2 = 5

Explanation: Left shifting by n positions multiplies the number by 2^n, while right shifting divides by 2^n (integer division).

3. Swap two variables without a temporary variable

java

// Before: a = 5, b = 7
a = a ^ b;  // a = 5 ^ 7
b = a ^ b;  // b = (5 ^ 7) ^ 7 = 5
a = a ^ b;  // a = (5 ^ 7) ^ 5 = 7
// After: a = 7, b = 5

// Example:
int x = 5, y = 7;
System.out.println("Before: x = " + x + ", y = " + y);
x = x ^ y;
y = x ^ y;
x = x ^ y;
System.out.println("After: x = " + x + ", y = " + y);
// Output:
// Before: x = 5, y = 7
// After: x = 7, y = 5

Explanation: This trick leverages the XOR operation's property that a ^ a = 0 and a ^ 0 = a. By applying XOR operations three times, we can swap values without using a temporary variable.

Intermediate Bitwise Tricks

1. Set, clear, and toggle bits

java

// Set the nth bit
int setBit(int num, int position) {
    return num | (1 << position);
}

// Clear the nth bit
int clearBit(int num, int position) {
    return num & ~(1 << position);
}

// Toggle the nth bit
int toggleBit(int num, int position) {
    return num ^ (1 << position);
}

// Check if the nth bit is set
boolean isBitSet(int num, int position) {
    return (num & (1 << position)) != 0;
}

// Example:
int number = 10;  // 1010 in binary
System.out.println("Original: " + Integer.toBinaryString(number));  // 1010
System.out.println("Set bit 0: " + Integer.toBinaryString(setBit(number, 0)));  // 1011
System.out.println("Clear bit 1: " + Integer.toBinaryString(clearBit(number, 1)));  // 1000
System.out.println("Toggle bit 3: " + Integer.toBinaryString(toggleBit(number, 3)));  // 0010
System.out.println("Is bit 3 set? " + isBitSet(number, 3));  // true

Explanation:

• Setting a bit uses OR with a shifted 1
• Clearing a bit uses AND with the complement of a shifted 1
• Toggling a bit uses XOR with a shifted 1
• Checking a bit uses AND with a shifted 1

2. Count the number of set bits (Hamming Weight)

java

// Method 1: Brian Kernighan's Algorithm
int countSetBits(int n) {
    int count = 0;
    while (n > 0) {
        n &= (n - 1);  // Clears the least significant set bit
        count++;
    }
    return count;
}

// Method 2: Lookup table for byte values
static int[] BIT_COUNT_TABLE = new int[256];
static {
    // Precompute bit counts for 0-255
    for (int i = 0; i < 256; i++) {
        BIT_COUNT_TABLE[i] = (i & 1) + BIT_COUNT_TABLE[i / 2];
    }
}

int countBits(int n) {
    // Count by bytes
    return BIT_COUNT_TABLE[n & 0xff] + 
           BIT_COUNT_TABLE[(n >> 8) & 0xff] + 
           BIT_COUNT_TABLE[(n >> 16) & 0xff] + 
           BIT_COUNT_TABLE[(n >> 24) & 0xff];
}

// Example:
int num = 122;  // 1111010 in binary
System.out.println("Number of set bits in " + num + ": " + countSetBits(num));  // Output: 5

Explanation: The first method uses a clever trick to clear the rightmost set bit in each iteration. The second method uses a lookup table for faster processing of larger numbers.

3. Find the rightmost set bit

java

// Find position of rightmost set bit
int getRightmostSetBitPos(int n) {
    if (n == 0) return 0;
    
    // Isolate the rightmost set bit
    int rightmost = n & -n;  // or n & (~n + 1)
    
    // Find position (log base 2)
    int position = 0;
    while (rightmost > 0) {
        rightmost >>= 1;
        position++;
    }
    
    return position;
}

// Example:
int num = 18;  // 10010 in binary
System.out.println("Position of rightmost set bit in " + num + ": " + 
                   getRightmostSetBitPos(num));  // Output: 2 (0-indexed)

Explanation: n & -n isolates the rightmost set bit because the two's complement of a number has all bits flipped except for the rightmost set bit.

Advanced Bitwise Tricks

1. Check if a number is a power of 2

java

boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

// Example:
int[] numbers = {1, 2, 4, 7, 8, 16};
for (int num : numbers) {
    System.out.println(num + " is power of 2: " + isPowerOfTwo(num));
}
// Output:
// 1 is power of 2: true
// 2 is power of 2: true
// 4 is power of 2: true
// 7 is power of 2: false
// 8 is power of 2: true
// 16 is power of 2: true

Explanation: A power of 2 has only one bit set in its binary representation. When we subtract 1 from it, all bits to the right of that bit become 1 and that bit becomes 0. For example, 8 (1000) - 1 = 7 (0111). By performing an AND operation, if the result is 0, the number is a power of 2.

2. Compute absolute value without branching

java

int abs(int n) {
    // Get the sign bit and extend it
    int mask = n >> 31;
    
    // If n is negative (mask = -1), this computes ~n + 1 (two's complement)
    // If n is positive (mask = 0), this returns n
    return (n + mask) ^ mask;
}

// Example:
System.out.println("Absolute of 42: " + abs(42));    // Output: 42
System.out.println("Absolute of -42: " + abs(-42));  // Output: 42

Explanation: This uses the sign bit (the most significant bit) to create a mask that's either all 0s (for positive numbers) or all 1s (for negative numbers). The expression then efficiently computes the absolute value without using if-statements.

3. Fast modulo for powers of 2

java

// Compute n % 2^k (equivalent to n % (1 << k))
int modPowerOf2(int n, int k) {
    return n & ((1 << k) - 1);
}

// Example:
int value = 100;
System.out.println(value + " % 8 = " + modPowerOf2(value, 3));  // 100 % 8 = 4
System.out.println(value + " % 16 = " + modPowerOf2(value, 4)); // 100 % 16 = 4

Explanation: For any power of 2, say 2^k, the remainder when dividing by 2^k is just the k least significant bits. This uses an AND operation with a mask of (2^k - 1) to extract those bits.

Practical Applications

Bit Flags for Compact Boolean Storage

java

class Permissions {
    private static final int READ = 1;       // 001
    private static final int WRITE = 1 << 1; // 010
    private static final int EXEC = 1 << 2;  // 100
    
    private int permissions;
    
    // Grant specific permission
    public void grant(int permission) {
        permissions |= permission;
    }
    
    // Check if has specific permission
    public boolean hasPermission(int permission) {
        return (permissions & permission) == permission;
    }
    
    // Revoke specific permission
    public void revoke(int permission) {
        permissions &= ~permission;
    }
}

// Example:
Permissions userPermissions = new Permissions();
userPermissions.grant(Permissions.READ);
userPermissions.grant(Permissions.WRITE);

System.out.println("Can read: " + userPermissions.hasPermission(Permissions.READ));     // true
System.out.println("Can write: " + userPermissions.hasPermission(Permissions.WRITE));   // true
System.out.println("Can execute: " + userPermissions.hasPermission(Permissions.EXEC));  // false

userPermissions.revoke(Permissions.WRITE);
System.out.println("Can write after revoke: " + userPermissions.hasPermission(Permissions.WRITE)); // false

Explanation: This is a common use case for bitwise operations in real-world applications. Using bit flags allows us to efficiently store multiple boolean values in a single integer.

Fast Color Operations with RGBA

java

class Color {
    private int rgba; // Format: AARRGGBB (Alpha, Red, Green, Blue)
    
    public Color(int red, int green, int blue, int alpha) {
        rgba = (alpha << 24) | (red << 16) | (green << 8) | blue;
    }
    
    public int getRed() {
        return (rgba >> 16) & 0xFF;
    }
    
    public int getGreen() {
        return (rgba >> 8) & 0xFF;
    }
    
    public int getBlue() {
        return rgba & 0xFF;
    }
    
    public int getAlpha() {
        return (rgba >> 24) & 0xFF;
    }
    
    public int getRGBA() {
        return rgba;
    }
}

// Example:
Color purple = new Color(128, 0, 128, 255); // Semi-transparent purple
System.out.println("Red: " + purple.getRed());     // 128
System.out.println("Green: " + purple.getGreen()); // 0
System.out.println("Blue: " + purple.getBlue());   // 128
System.out.println("Alpha: " + purple.getAlpha()); // 255
System.out.println("RGBA: 0x" + Integer.toHexString(purple.getRGBA())); // RGBA: 0xff8000ff

Explanation: This example shows how bitwise operations can efficiently store and manipulate color data, a common approach in graphics programming.

Summary

Bitwise tricks provide efficient solutions to many common programming problems. Let's recap some key points:

• Basic operations like checking for even/odd numbers, and multiplying/dividing by powers of 2
• Manipulation techniques like setting, clearing, and toggling bits
• Advanced algorithms for counting set bits and finding rightmost set bit
• Real-world applications like permissions systems and color manipulation

These tricks not only optimize your code but also deepen your understanding of how computers represent and manipulate data at the binary level.

Exercises

Test your understanding with these challenges:

1. Write a function to check if exactly one bit is set in a given integer.
2. Implement a function that returns the next power of 2 for a given number.
3. Create a function that determines if two integers have opposite signs without using if-statements.
4. Write a function to convert lowercase characters to uppercase using bitwise operations.
5. Implement a bit vector to efficiently store a set of integers from 0 to 63.

Additional Resources

• Bit Twiddling Hacks by Sean Eron Anderson
• Hacker's Delight by Henry S. Warren
• The Art of Computer Programming, Volume 4A by Donald Knuth

Learning bitwise tricks is a journey that will reward you with more efficient code and a deeper understanding of computational principles. Start applying these techniques in your projects, and you'll discover many opportunities for elegant optimizations!