Back to all blogs
    6 min read

    Java for DSA — Bit Manipulation & Characters

    JavaDsaBit-manipulationBitwiseCharactersXORBitmask

    8. Bit Manipulation & Characters

    Note

    Why this matters for DSA Bit manipulation allows for low-level O(1)O(1) bitwise operations that optimize both speed and memory (e.g., bitmask representation in subset problems, duplicate detection with XOR, and fast multiplication/division). Character handling is the foundation of string operations, frequency tracking, and parsing numbers out of raw text.

    8.1 Bitwise Operators

    Bitwise operators perform calculations on the binary representations of integers.

    java
    int a = 5;  // Binary: 0101
int b = 3;  // Binary: 0011

// 1. Bitwise AND (&) - returns 1 if both bits are 1
int and = a & b; // 0101 & 0011 = 0001 (1)

// 2. Bitwise OR (|) - returns 1 if at least one bit is 1
int or = a | b;  // 0101 | 0011 = 0111 (7)

// 3. Bitwise XOR (^) - returns 1 if bits are different
int xor = a ^ b; // 0101 ^ 0011 = 0110 (6)

// 4. Bitwise NOT (~) - inverts all bits (flips 0 to 1 and 1 to 0)
int not = ~a;    // ~0101 = 1010 (-6 in 2's complement)

// 5. Left Shift (<<) - shifts bits to the left, fills with 0 (multiplies by 2)
int leftShift = a << 1; // 0101 << 1 = 1010 (10)

// 6. Right Shift (>>) - shifts bits to the right, preserves sign (divides by 2)
int rightShift = a >> 1; // 0101 >> 1 = 0010 (2)

    8.2 Common Bit Manipulation Patterns

    These bit-level formulas appear frequently in optimization challenges:

    1. XOR Cancelation Properties (LeetCode "Single Number")

    • x⊕x=0x \oplus x = 0 (Any number XORed with itself cancels out to 0)
    • x⊕0=xx \oplus 0 = x (Any number XORed with 0 remains unchanged)

    2. Checking even/odd

    Instead of % 2 == 0, you can check the least significant bit:

    java
    if ((n & 1) == 0) {
    // Number is even
}

    3. Clear Lowest Set Bit (Kernighan's Algorithm)

    n & (n - 1) clears the lowest set (1) bit of a number.

    java
    int val = 12; // Binary: 1100
int cleared = val & (val - 1); // 1100 & 1011 = 1000 (8)

    4. Check Power of 2

    A positive integer is a power of 2 if it contains exactly one set bit in its binary representation.

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

    5. Manipulating the KK-th Bit (0-indexed from right)

    • Check KK-th bit: ((n >> k) & 1) == 1
    • Set KK-th bit to 1: n | (1 << k)
    • Clear KK-th bit to 0: n & ~(1 << k)
    • Toggle KK-th bit: n ^ (1 << k)

    6. Built-in Pop Count

    To count all set (1) bits in an integer:

    java
    int setBits = Integer.bitCount(29); // Binary: 11101 -> returns 4

    8.3 Character Handling

    The Character wrapper class provides essential static methods to inspect and manipulate single characters.

    java
    char c = 'A';

// 1. Classification
Character.isLetter(c);          // true
Character.isDigit(c);           // false
Character.isLetterOrDigit(c);   // true
Character.isWhitespace(' ');    // true
Character.isLowerCase(c);       // false
Character.isUpperCase(c);       // true

// 2. Case Conversion
char lower = Character.toLowerCase(c); // 'a'
char upper = Character.toUpperCase('b'); // 'B'

    8.4 Digit & ASCII Conversion Tricks

    In DSA, you want to avoid heavy object instantiation or string formatting. These O(1)O(1) mathematical conversion tricks are standard practice:

    1. Fast Char Digit to Integer

    Subtract the ASCII value of '0' from a digit character to get its integer value:

    java
    char digitChar = '7';
int val = digitChar - '0'; // 7 (no parsing methods needed!)

    2. Fast Integer to Char Digit

    Add the offset back and cast:

    java
    int num = 5;
char cVal = (char) (num + '0'); // '5'

    3. Case-Insensitive Alphabet Mappings (0 to 25)

    java
    // Lowercase mapping
char lowChar = 'd';
int lowIdx = lowChar - 'a'; // 3

// Uppercase mapping
char upChar = 'D';
int upIdx = upChar - 'A'; // 3

    Practice Drill

    java
    // Try implementing these:
// 1. Check if a given integer is odd using a bitwise operator.
// 2. Single Number: Given an array of integers where every element appears twice except for one, find that single one in O(n) time and O(1) space.
// 3. Implement Kernighan's Algorithm to count the number of set bits (1s) in an integer.
// 4. Given a string, check if it contains only alphanumeric characters (case-insensitive) using the Character class.
    💡 Click for Solutions
    java
    public class BitsCharsDrill {
    public static void main(String[] args) {
        // 1. Odd check
        System.out.println("Is 57 odd? " + isOdd(57)); // true

        // 2. Single Number
        int[] nums = {4, 1, 2, 1, 2};
        System.out.println("Single Number: " + findSingleNumber(nums)); // 4

        // 3. Set bits count
        System.out.println("Set bits in 29 (11101): " + countSetBits(29)); // 4

        // 4. Alphanumeric check
        System.out.println("Is 'LeetCode2026' alphanumeric? " + isAlphanumeric("LeetCode2026")); // true
        System.out.println("Is 'Hello World!' alphanumeric? " + isAlphanumeric("Hello World!")); // false
    }

    // 1. Odd check with bitwise AND
    public static boolean isOdd(int n) {
        return (n & 1) != 0;
    }

    // 2. Single Number with XOR
    public static int findSingleNumber(int[] nums) {
        int xorSum = 0;
        for (int num : nums) {
            xorSum ^= num;
        }
        return xorSum;
    }

    // 3. Kernighan's Algorithm
    public static int countSetBits(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1); // clears the lowest set bit
            count++;
        }
        return count;
    }

    // 4. Character check
    public static boolean isAlphanumeric(String s) {
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (!Character.isLetterOrDigit(ch)) {
                return false;
            }
        }
        return true;
    }
}

    ← Sorting & Utilities | Syllabus → Java Syllabus