August 22, 2023

Speaking the Language of Bits

A practical guide to understanding and using bitwise operators in Java for efficient low-level programming and data manipulation.

When working close to the metal - whether you're manipulating data structures, handling low-level tasks, or optimizing performance - bitwise operators are your best friends. Java, while being a high-level language, still offers solid support for bitwise operations that let you work with data at the bit level. In this comprehensive guide, we'll walk through Java's bitwise operators, explain what they do, and provide practical examples that demonstrate their power in real-world scenarios.

What Are Bitwise Operators?

Bitwise operators operate on the binary representations of integers. They allow you to manipulate individual bits directly, which can be incredibly useful for:

  • Performance optimization: Bitwise operations are among the fastest operations a CPU can perform
  • Memory efficiency: Packing multiple boolean values into a single integer
  • Low-level programming: Working with hardware, network protocols, or embedded systems
  • Cryptography: Implementing encryption algorithms and hash functions
  • Graphics programming: Color manipulation and pixel operations

Here's the complete list of bitwise operators in Java:

  • Bitwise AND (&): Returns 1 if both bits are 1
  • Bitwise OR (|): Returns 1 if either bit is 1
  • Bitwise XOR (^): Returns 1 if bits are different
  • Bitwise NOT (~): Inverts all bits
  • Left Shift (<<): Shifts bits left, filling with zeros
  • Right Shift (>>): Shifts bits right, preserving sign
  • Unsigned Right Shift (>>>): Shifts bits right, filling with zeros

Understanding Binary Representation

Before diving into operators, let's understand how Java represents integers in binary:

public class BinaryBasics {
    public static void main(String[] args) {
        int a = 12;  // Decimal

        // Different ways to represent the same number
        System.out.println("Decimal: " + a);
        System.out.println("Binary: " + Integer.toBinaryString(a));
        System.out.println("Hex: " + Integer.toHexString(a));

        // Binary literal (Java 7+)
        int b = 0b1100;  // Same as 12
        System.out.println("Binary literal: " + b);

        // Visualizing 32-bit representation
        System.out.printf("32-bit: %32s%n", Integer.toBinaryString(a).replace(' ', '0'));
    }
}

Output:

Decimal: 12
Binary: 1100
Hex: c
Binary literal: 12
32-bit: 00000000000000000000000000001100

Let's Break It Down With Examples

Bitwise AND (&)

Both bits must be 1 for the result to be 1. This is perfect for masking specific bits.

public class BitwiseAnd {
    public static void main(String[] args) {
        int a = 0b1100;  // 12 in decimal
        int b = 0b1010;  // 10 in decimal
        int result = a & b;

        System.out.println("a:      " + formatBinary(a));
        System.out.println("b:      " + formatBinary(b));
        System.out.println("a & b:  " + formatBinary(result));
        System.out.println("Result: " + result);  // 8
    }

    public static String formatBinary(int n) {
        return String.format("%4s", Integer.toBinaryString(n)).replace(' ', '0');
    }
}

Output:

a:      1100
b:      1010
a & b:  1000
Result: 8

Why it matters: Commonly used to:

  • Check if specific bits are set: if ((flags & MASK) != 0)
  • Extract specific bit ranges: int lowerByte = value & 0xFF
  • Clear specific bits: value & ~MASK

Bitwise OR (|)

If either bit is 1, the result is 1. Perfect for setting bits.

public class BitwiseOr {
    public static void main(String[] args) {
        int a = 0b1100;  // 12
        int b = 0b1010;  // 10
        int result = a | b;

        System.out.println("a:      " + formatBinary(a));
        System.out.println("b:      " + formatBinary(b));
        System.out.println("a | b:  " + formatBinary(result));
        System.out.println("Result: " + result);  // 14
    }

    public static String formatBinary(int n) {
        return String.format("%4s", Integer.toBinaryString(n)).replace(' ', '0');
    }
}

Output:

a:      1100
b:      1010
a | b:  1110
Result: 14

Why it matters: Used to:

  • Set specific bits: flags |= MASK
  • Combine bit patterns: permissions |= READ_PERMISSION | WRITE_PERMISSION
  • Create bit masks: int mask = BIT_1 | BIT_3 | BIT_5

Bitwise XOR (^)

If the bits are different, the result is 1. Great for toggling and encryption.

public class BitwiseXor {
    public static void main(String[] args) {
        int a = 0b1100;  // 12
        int b = 0b1010;  // 10
        int result = a ^ b;

        System.out.println("a:      " + formatBinary(a));
        System.out.println("b:      " + formatBinary(b));
        System.out.println("a ^ b:  " + formatBinary(result));
        System.out.println("Result: " + result);  // 6

        // XOR properties demonstration
        System.out.println("\nXOR Properties:");
        System.out.println("a ^ a = " + (a ^ a));  // Always 0
        System.out.println("a ^ 0 = " + (a ^ 0));  // Always a
        System.out.println("(a ^ b) ^ b = " + ((a ^ b) ^ b));  // Always a
    }

    public static String formatBinary(int n) {
        return String.format("%4s", Integer.toBinaryString(n)).replace(' ', '0');
    }
}

Output:

a:      1100
b:      1010
a ^ b:  0110
Result: 6

XOR Properties:
a ^ a = 0
a ^ 0 = 12
(a ^ b) ^ b = 12

Why it matters: XOR is special because:

  • It's its own inverse: (a ^ b) ^ b = a
  • Used in encryption and checksums
  • Perfect for toggling bits: flags ^= MASK
  • Can swap variables without temporary storage

Bitwise NOT (~)

Inverts every bit (1 becomes 0, 0 becomes 1).

public class BitwiseNot {
    public static void main(String[] args) {
        byte a = 0b00001111;  // 15
        int result = ~a;

        System.out.println("Original byte: " + formatBinary(a & 0xFF, 8));
        System.out.println("After NOT:     " + formatBinary(result, 32));
        System.out.println("Lower 8 bits:  " + formatBinary(result & 0xFF, 8));
        System.out.println("Decimal:       " + (result & 0xFF));  // 240
    }

    public static String formatBinary(int n, int bits) {
        String binary = Integer.toBinaryString(n);
        if (binary.length() > bits) {
            binary = binary.substring(binary.length() - bits);
        }
        return String.format("%" + bits + "s", binary).replace(' ', '0');
    }
}

Output:

Original byte: 00001111
After NOT:     11111111111111111111111111110000
Lower 8 bits:  11110000
Decimal:       240

Note: Java's ~ operator works on 32-bit signed integers, so you often need masking to see meaningful 8-bit output.

Left Shift (<<)

Shifts bits to the left, inserting zeros on the right. Equivalent to multiplying by powers of 2.

public class LeftShift {
    public static void main(String[] args) {
        int a = 0b0001;  // 1

        for (int i = 0; i <= 4; i++) {
            int shifted = a << i;
            System.out.printf("1 << %d = %4s = %2d (multiply by %d)%n",
                            i, formatBinary(shifted), shifted, (int)Math.pow(2, i));
        }

        // Practical example: Fast multiplication
        int number = 7;
        System.out.println("\nFast multiplication examples:");
        System.out.println(number + " * 2 = " + (number << 1));    // * 2
        System.out.println(number + " * 4 = " + (number << 2));    // * 4
        System.out.println(number + " * 8 = " + (number << 3));    // * 8
    }

    public static String formatBinary(int n) {
        return String.format("%4s", Integer.toBinaryString(n)).replace(' ', '0');
    }
}

Output:

1 << 0 = 0001 =  1 (multiply by 1)
1 << 1 = 0010 =  2 (multiply by 2)
1 << 2 = 0100 =  4 (multiply by 4)
1 << 3 = 1000 =  8 (multiply by 8)
1 << 4 = 0000 = 16 (multiply by 16)

Fast multiplication examples:
7 * 2 = 14
7 * 4 = 28
7 * 8 = 56

Right Shift (>>)

Shifts bits to the right, preserving the sign (arithmetic shift).

public class RightShift {
    public static void main(String[] args) {
        // Positive number
        int positive = 32;
        System.out.println("Positive number right shift:");
        for (int i = 0; i <= 3; i++) {
            int shifted = positive >> i;
            System.out.printf("%d >> %d = %s = %d%n",
                            positive, i, formatBinary(shifted), shifted);
        }

        // Negative number
        int negative = -32;
        System.out.println("\nNegative number right shift:");
        for (int i = 0; i <= 3; i++) {
            int shifted = negative >> i;
            System.out.printf("%d >> %d = %s = %d%n",
                            negative, i, formatBinary(shifted), shifted);
        }
    }

    public static String formatBinary(int n) {
        return String.format("%8s", Integer.toBinaryString(n)).replace(' ', '0');
    }
}

Unsigned Right Shift (>>>)

Fills with 0 from the left regardless of sign (logical shift).

public class UnsignedRightShift {
    public static void main(String[] args) {
        int negative = -8;

        System.out.println("Original: " + negative);
        System.out.println("Binary:   " + Integer.toBinaryString(negative));

        System.out.println("\nArithmetic right shift (>>):");
        System.out.println(negative + " >> 2 = " + (negative >> 2));
        System.out.println("Binary: " + Integer.toBinaryString(negative >> 2));

        System.out.println("\nLogical right shift (>>>):");
        System.out.println(negative + " >>> 2 = " + (negative >>> 2));
        System.out.println("Binary: " + Integer.toBinaryString(negative >>> 2));
    }
}

Output:

Original: -8
Binary:   11111111111111111111111111111000

Arithmetic right shift (>>):
-8 >> 2 = -2
Binary: 11111111111111111111111111111110

Logical right shift (>>>):
-8 >>> 2 = 1073741822
Binary: 111111111111111111111111111110

Real-World Applications

1. Flag Management in a Game Engine

Track entity states using bit flags for memory efficiency and fast operations:

public class GameEntity {
    // Define flag constants
    public static final int IS_VISIBLE = 1 << 0;        // 0001
    public static final int IS_ACTIVE = 1 << 1;         // 0010
    public static final int HAS_COLLISION = 1 << 2;     // 0100
    public static final int IS_PLAYER_CONTROLLED = 1 << 3; // 1000
    public static final int IS_ENEMY = 1 << 4;          // 10000
    public static final int IS_INVULNERABLE = 1 << 5;   // 100000

    private int flags;
    private String name;

    public GameEntity(String name) {
        this.name = name;
        this.flags = IS_VISIBLE | IS_ACTIVE; // Default state
    }

    // Set a flag
    public void setFlag(int flag) {
        flags |= flag;
        System.out.println(name + " set flag: " + getFlagName(flag));
    }

    // Clear a flag
    public void clearFlag(int flag) {
        flags &= ~flag;
        System.out.println(name + " cleared flag: " + getFlagName(flag));
    }

    // Toggle a flag
    public void toggleFlag(int flag) {
        flags ^= flag;
        System.out.println(name + " toggled flag: " + getFlagName(flag));
    }

    // Check if flag is set
    public boolean hasFlag(int flag) {
        return (flags & flag) != 0;
    }

    // Check multiple flags at once
    public boolean hasAllFlags(int flagMask) {
        return (flags & flagMask) == flagMask;
    }

    public boolean hasAnyFlag(int flagMask) {
        return (flags & flagMask) != 0;
    }

    public void printStatus() {
        System.out.println("\n" + name + " status:");
        System.out.println("Binary: " + String.format("%8s", Integer.toBinaryString(flags)).replace(' ', '0'));
        System.out.println("Visible: " + hasFlag(IS_VISIBLE));
        System.out.println("Active: " + hasFlag(IS_ACTIVE));
        System.out.println("Collision: " + hasFlag(HAS_COLLISION));
        System.out.println("Player Controlled: " + hasFlag(IS_PLAYER_CONTROLLED));
        System.out.println("Enemy: " + hasFlag(IS_ENEMY));
        System.out.println("Invulnerable: " + hasFlag(IS_INVULNERABLE));
    }

    private String getFlagName(int flag) {
        switch (flag) {
            case IS_VISIBLE: return "IS_VISIBLE";
            case IS_ACTIVE: return "IS_ACTIVE";
            case HAS_COLLISION: return "HAS_COLLISION";
            case IS_PLAYER_CONTROLLED: return "IS_PLAYER_CONTROLLED";
            case IS_ENEMY: return "IS_ENEMY";
            case IS_INVULNERABLE: return "IS_INVULNERABLE";
            default: return "UNKNOWN";
        }
    }

    public static void main(String[] args) {
        GameEntity player = new GameEntity("Player");

        // Player starts visible and active
        player.setFlag(HAS_COLLISION);
        player.setFlag(IS_PLAYER_CONTROLLED);

        player.printStatus();

        // Toggle visibility
        player.toggleFlag(IS_VISIBLE);
        player.printStatus();

        // Create an enemy
        GameEntity enemy = new GameEntity("Enemy");
        enemy.setFlag(IS_ENEMY);
        enemy.setFlag(HAS_COLLISION);
        enemy.clearFlag(IS_PLAYER_CONTROLLED);

        enemy.printStatus();

        // Check conditions
        if (player.hasAllFlags(IS_PLAYER_CONTROLLED | IS_ACTIVE)) {
            System.out.println("\nPlayer can be controlled!");
        }

        if (enemy.hasFlag(IS_ENEMY) && !enemy.hasFlag(IS_INVULNERABLE)) {
            System.out.println("Enemy can be damaged!");
        }
    }
}

2. Fast Color Manipulation

Extract and manipulate RGB values from a 24-bit color efficiently:

public class ColorManipulation {

    // Extract RGB components from a 24-bit color
    public static int[] extractRGB(int color) {
        int r = (color >> 16) & 0xFF;  // Get red component
        int g = (color >> 8) & 0xFF;   // Get green component
        int b = color & 0xFF;          // Get blue component
        return new int[]{r, g, b};
    }

    // Create color from RGB components
    public static int createColor(int r, int g, int b) {
        return (r << 16) | (g << 8) | b;
    }

    // Extract RGBA components from a 32-bit color
    public static int[] extractRGBA(int color) {
        int a = (color >> 24) & 0xFF;  // Alpha
        int r = (color >> 16) & 0xFF;  // Red
        int g = (color >> 8) & 0xFF;   // Green
        int b = color & 0xFF;          // Blue
        return new int[]{r, g, b, a};
    }

    // Create RGBA color
    public static int createRGBA(int r, int g, int b, int a) {
        return (a << 24) | (r << 16) | (g << 8) | b;
    }

    // Blend two colors (simple alpha blending)
    public static int blendColors(int color1, int color2, float alpha) {
        int[] rgb1 = extractRGB(color1);
        int[] rgb2 = extractRGB(color2);

        int r = (int)(rgb1[0] * (1 - alpha) + rgb2[0] * alpha);
        int g = (int)(rgb1[1] * (1 - alpha) + rgb2[1] * alpha);
        int b = (int)(rgb1[2] * (1 - alpha) + rgb2[2] * alpha);

        return createColor(r, g, b);
    }

    // Darken a color by reducing all components
    public static int darken(int color, float factor) {
        int[] rgb = extractRGB(color);
        int r = (int)(rgb[0] * factor);
        int g = (int)(rgb[1] * factor);
        int b = (int)(rgb[2] * factor);
        return createColor(r, g, b);
    }

    // Convert color to grayscale
    public static int toGrayscale(int color) {
        int[] rgb = extractRGB(color);
        // Using luminance formula: 0.299*R + 0.587*G + 0.114*B
        int gray = (int)(rgb[0] * 0.299 + rgb[1] * 0.587 + rgb[2] * 0.114);
        return createColor(gray, gray, gray);
    }

    public static void main(String[] args) {
        int purple = 0xA020F0;  // Purple color
        int orange = 0xFF8C00;  // Orange color

        System.out.println("Purple (#A020F0):");
        int[] purpleRGB = extractRGB(purple);
        System.out.printf("R: %d, G: %d, B: %d%n", purpleRGB[0], purpleRGB[1], purpleRGB[2]);
        System.out.printf("Hex: #%06X%n", purple);

        System.out.println("\nOrange (#FF8C00):");
        int[] orangeRGB = extractRGB(orange);
        System.out.printf("R: %d, G: %d, B: %d%n", orangeRGB[0], orangeRGB[1], orangeRGB[2]);
        System.out.printf("Hex: #%06X%n", orange);

        // Blend colors
        int blended = blendColors(purple, orange, 0.5f);
        System.out.println("\n50/50 Blend:");
        int[] blendedRGB = extractRGB(blended);
        System.out.printf("R: %d, G: %d, B: %d%n", blendedRGB[0], blendedRGB[1], blendedRGB[2]);
        System.out.printf("Hex: #%06X%n", blended);

        // Darken purple
        int darkPurple = darken(purple, 0.6f);
        System.out.println("\nDarkened Purple (60%):");
        System.out.printf("Hex: #%06X%n", darkPurple);

        // Convert to grayscale
        int grayPurple = toGrayscale(purple);
        System.out.println("\nPurple in Grayscale:");
        System.out.printf("Hex: #%06X%n", grayPurple);
    }
}

3. Power of Two Operations

Efficiently work with powers of two using bit manipulation:

public class PowerOfTwoOperations {

    // Check if a number is a power of two
    public static boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }

    // Find the next power of two greater than or equal to n
    public static int nextPowerOfTwo(int n) {
        if (n <= 1) return 1;

        // Handle the case where n is already a power of two
        if (isPowerOfTwo(n)) return n;

        // Find the highest set bit and double it
        n--;
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        return n + 1;
    }

    // Find the previous power of two less than or equal to n
    public static int previousPowerOfTwo(int n) {
        if (n <= 1) return 1;

        // Find the highest set bit
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        return n - (n >> 1);
    }

    // Fast modulo for power of two divisors
    public static int fastModulo(int dividend, int powerOfTwoDivisor) {
        if (!isPowerOfTwo(powerOfTwoDivisor)) {
            throw new IllegalArgumentException("Divisor must be a power of two");
        }
        return dividend & (powerOfTwoDivisor - 1);
    }

    // Round up to nearest multiple of power of two
    public static int roundUpToMultiple(int n, int powerOfTwo) {
        if (!isPowerOfTwo(powerOfTwo)) {
            throw new IllegalArgumentException("Must be a power of two");
        }
        return (n + powerOfTwo - 1) & ~(powerOfTwo - 1);
    }

    // Round down to nearest multiple of power of two
    public static int roundDownToMultiple(int n, int powerOfTwo) {
        if (!isPowerOfTwo(powerOfTwo)) {
            throw new IllegalArgumentException("Must be a power of two");
        }
        return n & ~(powerOfTwo - 1);
    }

    public static void main(String[] args) {
        System.out.println("Power of Two Checks:");
        int[] testNumbers = {1, 2, 3, 4, 8, 15, 16, 32, 33, 64};
        for (int num : testNumbers) {
            System.out.printf("%2d is power of two: %s%n", num, isPowerOfTwo(num));
        }

        System.out.println("\nNext/Previous Power of Two:");
        int[] testValues = {5, 9, 17, 31, 100};
        for (int val : testValues) {
            System.out.printf("Value: %3d, Previous: %3d, Next: %3d%n",
                            val, previousPowerOfTwo(val), nextPowerOfTwo(val));
        }

        System.out.println("\nFast Modulo (% 16):");
        for (int i = 0; i < 20; i++) {
            int regular = i % 16;
            int fast = fastModulo(i, 16);
            System.out.printf("%2d %% 16 = %2d (fast: %2d) %s%n",
                            i, regular, fast, regular == fast ? "✓" : "✗");
        }

        System.out.println("\nRounding to multiples of 8:");
        int[] values = {7, 8, 9, 15, 16, 17, 23, 24, 25};
        for (int val : values) {
            System.out.printf("Value: %2d, Round down: %2d, Round up: %2d%n",
                            val, roundDownToMultiple(val, 8), roundUpToMultiple(val, 8));
        }
    }
}

4. Bit Counting and Analysis

Various algorithms for counting and analyzing bits:

public class BitAnalysis {

    // Count set bits (population count) - Brian Kernighan's algorithm
    public static int countSetBits(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n &= (n - 1); // Remove the rightmost set bit
        }
        return count;
    }

    // Count set bits using built-in method (most efficient)
    public static int countSetBitsBuiltIn(int n) {
        return Integer.bitCount(n);
    }

    // Count trailing zeros
    public static int countTrailingZeros(int n) {
        if (n == 0) return 32;

        int count = 0;
        while ((n & 1) == 0) {
            count++;
            n >>= 1;
        }
        return count;
    }

    // Count leading zeros
    public static int countLeadingZeros(int n) {
        if (n == 0) return 32;

        int count = 0;
        for (int i = 31; i >= 0; i--) {
            if ((n & (1 << i)) != 0) break;
            count++;
        }
        return count;
    }

    // Find position of rightmost set bit (1-indexed)
    public static int findRightmostSetBit(int n) {
        if (n == 0) return 0;
        return countTrailingZeros(n) + 1;
    }

    // Get the value of the rightmost set bit
    public static int getRightmostSetBit(int n) {
        return n & -n;  // Isolate rightmost set bit
    }

    // Check if bits at positions i and j are different
    public static boolean bitsDiffer(int n, int i, int j) {
        return ((n >> i) & 1) != ((n >> j) & 1);
    }

    // Reverse the bits of an integer
    public static int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);
            n >>= 1;
        }
        return result;
    }

    // Check if number has alternating bits (101010... or 010101...)
    public static boolean hasAlternatingBits(int n) {
        int xor = n ^ (n >> 1);
        return (xor & (xor + 1)) == 0;
    }

    public static void main(String[] args) {
        int[] testNumbers = {0b1101, 0b1111, 0b1000, 0b1010101, 0b0};

        System.out.println("Bit Analysis:");
        System.out.println("Num\tBinary\t\tSet Bits\tTrailing 0s\tLeading 0s\tRightmost Set");
        System.out.println("---\t------\t\t--------\t-----------\t----------\t-------------");

        for (int num : testNumbers) {
            String binary = String.format("%8s", Integer.toBinaryString(num)).replace(' ', '0');
            int setBits = countSetBits(num);
            int trailingZeros = countTrailingZeros(num);
            int leadingZeros = countLeadingZeros(num);
            int rightmostSet = findRightmostSetBit(num);

            System.out.printf("%d\t%s\t%d\t\t%d\t\t%d\t\t%d%n",
                            num, binary, setBits, trailingZeros, leadingZeros, rightmostSet);
        }

        System.out.println("\nSpecial Properties:");
        for (int num : testNumbers) {
            System.out.printf("0b%s: Alternating bits? %s%n",
                            Integer.toBinaryString(num), hasAlternatingBits(num));
        }

        // Demonstrate bit reversal
        int original = 0b11010000;
        int reversed = reverseBits(original);
        System.out.printf("\nBit Reversal:%n");
        System.out.printf("Original: %s%n", String.format("%32s", Integer.toBinaryString(original)).replace(' ', '0'));
        System.out.printf("Reversed: %s%n", String.format("%32s", Integer.toBinaryString(reversed)).replace(' ', '0'));
    }
}

5. XOR-Based Algorithms

XOR has unique properties that make it useful for various algorithms:

public class XORAlgorithms {

    // Swap two variables without temporary variable
    public static void swapWithoutTemp(int[] arr, int i, int j) {
        if (i != j) {  // Important: don't swap with itself
            arr[i] = arr[i] ^ arr[j];
            arr[j] = arr[i] ^ arr[j];
            arr[i] = arr[i] ^ arr[j];
        }
    }

    // Find the single number in array where every other number appears twice
    public static int findSingle(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;  // All pairs cancel out, leaving the single number
    }

    // Find two numbers that appear once in array where others appear twice
    public static int[] findTwoSingles(int[] nums) {
        // XOR all numbers - result will be XOR of the two single numbers
        int xorResult = 0;
        for (int num : nums) {
            xorResult ^= num;
        }

        // Find a bit where the two numbers differ
        int differingBit = xorResult & -xorResult;  // Rightmost set bit

        // Partition numbers based on this bit and XOR each partition
        int first = 0, second = 0;
        for (int num : nums) {
            if ((num & differingBit) == 0) {
                first ^= num;
            } else {
                second ^= num;
            }
        }

        return new int[]{first, second};
    }

    // Simple encryption/decryption using XOR
    public static String xorEncrypt(String text, String key) {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < text.length(); i++) {
            char encrypted = (char)(text.charAt(i) ^ key.charAt(i % key.length()));
            result.append(encrypted);
        }
        return result.toString();
    }

    public static String xorDecrypt(String encryptedText, String key) {
        return xorEncrypt(encryptedText, key);  // XOR is its own inverse
    }

    // Check if a number is even or odd using XOR
    public static boolean isEven(int n) {
        return (n & 1) == 0;
    }

    // Toggle case of alphabetic characters
    public static char toggleCase(char c) {
        if (Character.isLetter(c)) {
            return (char)(c ^ 32);  // 32 = 0b100000, flips the case bit
        }
        return c;
    }

    // Missing number in range 1 to n
    public static int findMissingNumber(int[] nums, int n) {
        int expected = 0, actual = 0;

        // XOR all numbers from 1 to n
        for (int i = 1; i <= n; i++) {
            expected ^= i;
        }

        // XOR all numbers in array
        for (int num : nums) {
            actual ^= num;
        }

        // The result is the missing number
        return expected ^ actual;
    }

    public static void main(String[] args) {
        // Demonstrate swapping
        int[] arr = {5, 7};
        System.out.println("Before swap: " + Arrays.toString(arr));
        swapWithoutTemp(arr, 0, 1);
        System.out.println("After swap: " + Arrays.toString(arr));

        // Find single number
        int[] singleArray = {2, 2, 1, 1, 4, 4, 3};
        System.out.println("\nArray with one single: " + Arrays.toString(singleArray));
        System.out.println("Single number: " + findSingle(singleArray));

        // Find two single numbers
        int[] twoSinglesArray = {1, 2, 1, 3, 2, 5};
        System.out.println("\nArray with two singles: " + Arrays.toString(twoSinglesArray));
        System.out.println("Two single numbers: " + Arrays.toString(findTwoSingles(twoSinglesArray)));

        // XOR encryption
        String message = "Hello World!";
        String key = "SECRET";
        String encrypted = xorEncrypt(message, key);
        String decrypted = xorDecrypt(encrypted, key);

        System.out.println("\nXOR Encryption:");
        System.out.println("Original:  " + message);
        System.out.println("Key:       " + key);
        System.out.println("Encrypted: " + encrypted);
        System.out.println("Decrypted: " + decrypted);

        // Case toggling
        String text = "Hello World!";
        System.out.println("\nCase Toggling:");
        System.out.println("Original: " + text);
        StringBuilder toggled = new StringBuilder();
        for (char c : text.toCharArray()) {
            toggled.append(toggleCase(c));
        }
        System.out.println("Toggled:  " + toggled.toString());

        // Find missing number
        int[] incomplete = {1, 2, 4, 5, 6};  // Missing 3 from 1-6
        int missing = findMissingNumber(incomplete, 6);
        System.out.println("\nMissing number from " + Arrays.toString(incomplete) + ": " + missing);
    }
}

Advanced Bit Manipulation Techniques

Bit Manipulation for Data Structures

public class BitSet {
    private long[] bits;
    private int size;

    public BitSet(int size) {
        this.size = size;
        this.bits = new long[(size + 63) / 64];  // Round up division
    }

    public void set(int index) {
        if (index >= size) throw new IndexOutOfBoundsException();
        int wordIndex = index / 64;
        int bitIndex = index % 64;
        bits[wordIndex] |= (1L << bitIndex);
    }

    public void clear(int index) {
        if (index >= size) throw new IndexOutOfBoundsException();
        int wordIndex = index / 64;
        int bitIndex = index % 64;
        bits[wordIndex] &= ~(1L << bitIndex);
    }

    public boolean get(int index) {
        if (index >= size) throw new IndexOutOfBoundsException();
        int wordIndex = index / 64;
        int bitIndex = index % 64;
        return (bits[wordIndex] & (1L << bitIndex)) != 0;
    }

    public void flip(int index) {
        if (index >= size) throw new IndexOutOfBoundsException();
        int wordIndex = index / 64;
        int bitIndex = index % 64;
        bits[wordIndex] ^= (1L << bitIndex);
    }

    public int cardinality() {
        int count = 0;
        for (long word : bits) {
            count += Long.bitCount(word);
        }
        return count;
    }

    public BitSet and(BitSet other) {
        BitSet result = new BitSet(Math.min(this.size, other.size));
        int minWords = Math.min(this.bits.length, other.bits.length);
        for (int i = 0; i < minWords; i++) {
            result.bits[i] = this.bits[i] & other.bits[i];
        }
        return result;
    }

    public BitSet or(BitSet other) {
        BitSet result = new BitSet(Math.max(this.size, other.size));
        for (int i = 0; i < result.bits.length; i++) {
            long thisBits = i < this.bits.length ? this.bits[i] : 0;
            long otherBits = i < other.bits.length ? other.bits[i] : 0;
            result.bits[i] = thisBits | otherBits;
        }
        return result;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < size; i++) {
            sb.append(get(i) ? '1' : '0');
        }
        return sb.toString();
    }
}

Performance Considerations

Bitwise operations are extremely fast because they're implemented directly in hardware. Here are some performance tips:

Fast Arithmetic Operations

public class FastArithmetic {

    // Multiply by powers of 2
    public static int multiplyByPowerOf2(int n, int power) {
        return n << power;  // Much faster than n * (2^power)
    }

    // Divide by powers of 2 (for positive numbers)
    public static int divideByPowerOf2(int n, int power) {
        return n >> power;  // Much faster than n / (2^power)
    }

    // Fast modulo for powers of 2
    public static int moduloPowerOf2(int n, int powerOf2) {
        return n & (powerOf2 - 1);  // Much faster than n % powerOf2
    }

    // Fast absolute value (works for most cases, be careful with Integer.MIN_VALUE)
    public static int fastAbs(int n) {
        int mask = n >> 31;  // All 1s if negative, all 0s if positive
        return (n ^ mask) - mask;
    }

    // Check if two integers have opposite signs
    public static boolean oppositeSigns(int a, int b) {
        return (a ^ b) < 0;
    }

    // Fast min/max without branching
    public static int fastMin(int a, int b) {
        return b ^ ((a ^ b) & -(a < b ? 1 : 0));
    }

    public static int fastMax(int a, int b) {
        return a ^ ((a ^ b) & -(a < b ? 1 : 0));
    }

    public static void main(String[] args) {
        System.out.println("Fast Arithmetic Demonstrations:");

        // Multiplication
        int n = 7;
        System.out.printf("%d << 3 = %d (same as %d * 8)%n",
                        n, multiplyByPowerOf2(n, 3), n * 8);

        // Division
        n = 64;
        System.out.printf("%d >> 3 = %d (same as %d / 8)%n",
                        n, divideByPowerOf2(n, 3), n / 8);

        // Modulo
        n = 23;
        System.out.printf("%d & 15 = %d (same as %d %% 16)%n",
                        n, moduloPowerOf2(n, 16), n % 16);

        // Absolute value
        int[] testValues = {-42, 42, 0, -1, 1};
        for (int val : testValues) {
            System.out.printf("fastAbs(%d) = %d, Math.abs(%d) = %d%n",
                            val, fastAbs(val), val, Math.abs(val));
        }

        // Opposite signs
        System.out.printf("oppositeSigns(5, -3): %s%n", oppositeSigns(5, -3));
        System.out.printf("oppositeSigns(5, 3): %s%n", oppositeSigns(5, 3));

        // Fast min/max
        int a = 15, b = 7;
        System.out.printf("fastMin(%d, %d) = %d%n", a, b, fastMin(a, b));
        System.out.printf("fastMax(%d, %d) = %d%n", a, b, fastMax(a, b));
    }
}

Common Pitfalls and How to Avoid Them

1. Operator Precedence

Be careful with operator precedence. Bitwise operators have lower precedence than comparison operators:

public class OperatorPrecedence {
    public static void main(String[] args) {
        int flags = 0b1010;
        int mask = 0b0010;

        // Wrong - this checks if (flags & mask) equals 0, then compares that boolean to 0
        // if (flags & mask == 0) { ... }  // DON'T DO THIS

        // Correct - use parentheses
        if ((flags & mask) == 0) {
            System.out.println("Bit is not set");
        } else {
            System.out.println("Bit is set");
        }

        // Or check for non-zero
        if ((flags & mask) != 0) {
            System.out.println("Bit is set");
        }
    }
}

2. Sign Extension with Right Shift

Be aware of sign extension when working with negative numbers:

public class SignExtension {
    public static void main(String[] args) {
        int negative = -8;

        System.out.println("Original: " + negative);
        System.out.println("Binary: " + Integer.toBinaryString(negative));

        // Arithmetic right shift preserves sign
        System.out.println(">> 1: " + (negative >> 1));
        System.out.println("Binary: " + Integer.toBinaryString(negative >> 1));

        // Logical right shift fills with zeros
        System.out.println(">>> 1: " + (negative >>> 1));
        System.out.println("Binary: " + Integer.toBinaryString(negative >>> 1));

        // Working with bytes - be careful of sign extension
        byte b = -1;  // 0xFF
        int extended = b;  // Becomes 0xFFFFFFFF
        int masked = b & 0xFF;  // Becomes 0x000000FF

        System.out.printf("Byte: %02X, Extended: %08X, Masked: %08X%n",
                        b & 0xFF, extended, masked);
    }
}

3. Overflow in Left Shift

Shifting too far left can cause overflow:

public class ShiftOverflow {
    public static void main(String[] args) {
        int value = 1;

        System.out.println("Left shift overflow demonstration:");
        for (int i = 28; i <= 32; i++) {
            int shifted = value << i;
            System.out.printf("1 << %d = %d (0x%08X)%n", i, shifted, shifted);
        }

        // Safe shifting with bounds checking
        public static int safeLeftShift(int value, int positions) {
            if (positions < 0 || positions >= 32) {
                throw new IllegalArgumentException("Shift positions must be 0-31");
            }

            // Check for overflow
            if (value != 0 && positions >= Integer.numberOfLeadingZeros(Math.abs(value))) {
                throw new ArithmeticException("Left shift would cause overflow");
            }

            return value << positions;
        }
    }
}

Conclusion

Bitwise operations are a powerful tool in the Java programmer's arsenal. While Java abstracts away many low-level details, understanding and leveraging bitwise operations can lead to:

  • Significant performance improvements in computational intensive applications
  • Memory-efficient data structures that pack more information into less space
  • Elegant solutions to complex problems like state management and data manipulation
  • Better understanding of how computers work at the fundamental level

Key takeaways for mastering bitwise operations:

  1. Start simple: Begin with basic flag operations and gradually work up to more complex algorithms
  2. Practice regularly: Implement the examples in this guide and experiment with variations
  3. Understand the binary: Always think about what's happening at the bit level
  4. Use appropriate tools: Leverage Integer.toBinaryString() and similar utilities for debugging
  5. Consider readability: While bitwise operations are fast, sometimes clear code is more important than micro-optimizations
  6. Test thoroughly: Bitwise code can be tricky to debug, so write comprehensive tests

Whether you're building game engines, working with graphics, implementing cryptographic algorithms, or simply optimizing performance-critical code, mastering bitwise operations will make you a more effective and versatile programmer.

Remember: with great power comes great responsibility. Use these techniques judiciously, document your bit manipulation code well, and always consider maintainability alongside performance. Happy bit twiddling!

Tags

#Java
#Programming
#Performance
#Low-level
Published on August 22, 2023