DSA Series: Binary / Bit Manipulation (Blind 75, Java)

Overview

• Pattern cheat-sheet
• 1. Sum of Two Integers
• 2. Number of 1 Bits
• 3. Counting Bits
• 4. Missing Number
• 5. Reverse Bits

Part of the DSA Blind 75 series. Track your progress on the Interview Prep page.

All Java solutions in this file were compiled with javac and checked with assertions (examples, edge cases, and 100k randomized comparisons against Integer.bitCount, Integer.reverse, +, etc.).

Pattern cheat-sheet

Java reminders: int is 32-bit two's complement; >> is arithmetic (sign-extending), >>> is logical (zero-fill) - use >>> when treating the value as unsigned. Library helpers: Integer.bitCount, Integer.reverse, Integer.toBinaryString, Integer.toUnsignedLong.

1. Sum of Two Integers

(Medium · LeetCode #371)

Problem statement Return a + b without using the operators + and -.

• a = 1, b = 2 -> 3
• a = 2, b = 3 -> 5
• Constraints: -1000 <= a, b <= 1000.

How the interviewer asks / follow-ups

• Disguised: "Implement the adder of a hardware/ALU-style checksum", or "how does a CPU add two numbers?"; in payments, relevant to understanding integer overflow in amount arithmetic (minor units, e.g. paise/cents).
• Follow-ups: how does it handle negatives (two's complement; the same loop works for 32-bit int in Java because shifts discard overflow bits)? Subtraction without - (a + (~b + 1))? Why does the loop terminate (carry shifts left each iteration, at most 32 iterations)? What happens on overflow (Integer.MAX_VALUE + 1 wraps to MIN_VALUE, same as +)? Multiply without * (shift-and-add)? For money in production use Math.addExact to detect overflow.
• Evaluating: comfort with bitwise logic and two's complement.

Approach 1: Brute force Increment a by one b times (or decrement if b < 0). Uses ++/--, which technically sidesteps the rule, and is O(|b|). It is fine only for the tiny constraint and as a baseline.

Approach 2: XOR + carry loop

• Intuition: bitwise, a ^ b is the sum of each bit position ignoring carries; (a & b) << 1 is exactly the carries moved to the next position. Then a + b = (a ^ b) + carry, so repeat with those two values until the carry is 0.
• Dry run 2 + 3: a=010, b=011. carry=(010)<<1=100, a=001, b=100. carry=(000)<<1=0, a=101, b=0. Result 5.
• Negatives work automatically because Java ints are two's complement and the loop operates on all 32 bits (in Python you'd need a mask).

Java code

class SumOfTwoIntegers {
    // Brute force: O(|b|) time, O(1) space (baseline only)
    static int getSumBrute(int a, int b) {
        if (b > 0) for (int i = 0; i < b; i++) a++;
        else for (int i = 0; i < -b; i++) a--;
        return a;
    }

    // Optimal: O(1) time (<= 32 iterations), O(1) space
    static int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1; // bits where both are 1 produce a carry to the left
            a = a ^ b;                // sum without carry
            b = carry;                // add the carry in the next round
        }
        return a;
    }
}

Complexity

• Brute force: Time O(|b|), Space O(1).
• XOR/carry: Time O(w) = O(32) = O(1) (the carry moves at least one bit left each pass), Space O(1).

Edge cases / pitfalls

• Negative operands and mixed signs (-1 + 1 = 0, -2 + -3 = -5).
• Overflow: getSum(Integer.MAX_VALUE, 1) returns Integer.MIN_VALUE, identical to +.
• Use << on int (not long) so bits beyond 32 are discarded and the loop terminates.

Pattern & related problems Bitwise full-adder emulation. Related: #191 Number of 1 Bits, #136 Single Number, #67 Add Binary, #43 Multiply Strings, #29 Divide Two Integers.

2. Number of 1 Bits

(Easy · LeetCode #191)

Problem statement Return the number of set bits (1s) in the binary representation of an unsigned 32-bit integer (Hamming weight).

• n = 11 (1011) -> 3
• n = 128 (10000000) -> 1
• n = 2147483645 (0111...1101) -> 30. In Java the input arrives as a signed int, so -3 (0xFFFFFFFD) -> 31.
• Constraint: input is a 32-bit binary string / int.

How the interviewer asks / follow-ups

• Disguised: "A permissions or feature-flag word stores each flag as a bit; how many flags are enabled?" or "popcount of a bitmap of settled transactions". Also parity checks, bloom filter fill ratio.
• Follow-ups: do it in time proportional to the number of set bits (Kernighan); called many times - use an 8-bit lookup table or the SWAR trick; is n a power of two (n > 0 && (n & (n-1)) == 0, #231)? Hamming distance between two numbers (bitCount(x ^ y), #461); what does Integer.bitCount do (HW popcnt intrinsic).
• Evaluating: knowing n & (n-1) and handling the sign bit correctly in Java.

Approach 1: Brute force (check each bit) Loop 32 times, test bit i with (n >>> i) & 1. Time O(32), space O(1). Use >>>, or loop with a mask 1 << i.

Approach 2: Brian Kernighan

• Intuition: n & (n - 1) clears the lowest set bit (subtracting 1 flips the lowest set bit to 0 and all bits below it to 1). So the number of iterations until n == 0 equals the number of set bits.
• Dry run n = 1011: 1011 & 1010 = 1010 (1), 1010 & 1001 = 1000 (2), 1000 & 0111 = 0 (3). Answer 3.
• Works for negatives too, since the loop condition is n != 0 (not n > 0).

Java code

class NumberOfOneBits {
    // Brute force: check all 32 bits
    static int hammingBrute(int n) {
        int c = 0;
        for (int i = 0; i < 32; i++)
            if (((n >>> i) & 1) == 1) c++;   // >>> so the sign bit is treated as data
        return c;
    }

    // Optimal: Kernighan, one iteration per set bit
    static int hammingWeight(int n) {
        int c = 0;
        while (n != 0) {      // != 0, NOT > 0: negative ints have the sign bit set
            n &= (n - 1);     // clear the lowest set bit
            c++;
        }
        return c;
    }
}

Complexity

• Brute force: Time O(32) = O(1), Space O(1).
• Kernighan: Time O(k) where k = number of set bits (at most 32), Space O(1).

Edge cases / pitfalls

• n = 0 -> 0. n = -1 (all ones) -> 32. Integer.MIN_VALUE -> 1.
• Using n > 0 as the loop condition or >> (arithmetic shift) on negatives loops forever or miscounts.
• Java has no unsigned int - the sign bit is just bit 31.

Pattern & related problems n & (n-1) lowest-set-bit trick. Related: #338 Counting Bits, #231 Power of Two, #461 Hamming Distance, #136 Single Number, #190 Reverse Bits.

3. Counting Bits

(Easy · LeetCode #338)

Problem statement Given n, return an array ans of length n + 1 where ans[i] is the number of 1s in the binary form of i.

• n = 2 -> [0,1,1]
• n = 5 -> [0,1,1,2,1,2]
• Constraints: 0 <= n <= 1e5. Follow-up: do it in O(n) total time, in a single pass, without a built-in popcount.

How the interviewer asks / follow-ups

• Disguised: "Precompute a popcount table for all 16-bit codes (e.g. a lookup table for a bitmap index / ISO 8583 bitmap field)", or "number of enabled features for each permission mask 0..n".
• Follow-ups: O(n) instead of O(n log n); DP recurrences (i >> 1, i & (i-1), highest power of two offset); O(1) extra space besides output; lookup tables for popcount of 32-bit values with two 16-bit lookups.
• Evaluating: DP reuse of subproblems, linking to #191.

Approach 1: Brute force Compute popcount of each i independently with Kernighan. Time O(n log n) (up to log n bits each), space O(1) beyond output.

Approach 2: DP using the right shift

• Intuition: i >> 1 drops the last bit, so bits(i) = bits(i >> 1) + (i & 1). i >> 1 < i is already computed.
• Alternative recurrence: dp[i] = dp[i & (i - 1)] + 1 (clearing the lowest set bit removes exactly one bit).
• Dry run n=5: dp[0]=0; dp[1]=dp[0]+1=1; dp[2]=dp[1]+0=1; dp[3]=dp[1]+1=2; dp[4]=dp[2]+0=1; dp[5]=dp[2]+1=2 -> [0,1,1,2,1,2].

Java code

class CountingBits {
    // Brute force: O(n log n)
    static int[] countBitsBrute(int n) {
        int[] r = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int x = i, c = 0;
            while (x != 0) { x &= (x - 1); c++; }
            r[i] = c;
        }
        return r;
    }

    // Optimal DP: O(n) time, O(1) extra space besides output
    static int[] countBits(int n) {
        int[] dp = new int[n + 1];              // dp[0] = 0
        for (int i = 1; i <= n; i++)
            dp[i] = dp[i >> 1] + (i & 1);       // bits of i/2 plus the last bit
        return dp;
    }
}

Complexity

• Brute force: Time O(n log n), Space O(1) extra.
• DP: Time O(n) (one O(1) step per index), Space O(1) extra (the output array is required).

Edge cases / pitfalls

• n = 0 -> [0] (array of size n+1, do not read dp[1]). Index 0 must be 0.
• Use >> (non-negative values so same as >>>); do not call Integer.bitCount if the interviewer says no built-ins.
• Off-by-one: length is n + 1.

Pattern & related problems DP on bits / reuse of smaller subproblems. Related: #191 Number of 1 Bits, #231 Power of Two, #461 Hamming Distance, #1356 Sort Integers by Number of 1 Bits.

4. Missing Number

(Easy · LeetCode #268)

Problem statement Given an array nums of n distinct numbers in the range [0, n], return the one number in the range that is missing.

• [3,0,1] -> 2
• [0,1] -> 2
• [9,6,4,2,3,5,7,0,1] -> 8
• Constraints: 1 <= n <= 1e4, all distinct. Follow-up: O(1) extra space, O(n) time.

How the interviewer asks / follow-ups

• Disguised: "Transactions in a batch carry sequence numbers 0..n; exactly one is missing - find the dropped message" (gap detection in a settlement file); "one of n sequential reference numbers was never received".
• Follow-ups: sum formula and its overflow risk (n(n+1)/2 can overflow for large n - use long, or use XOR); two numbers missing (use sum and sum of squares, or XOR partition by lowest differing bit); one number duplicated and one missing (#645, #287); array not distinct; sorted input (binary search, O(log n)); streaming sequence numbers (maintain running XOR/sum); data too large for memory (bitmap / range counts).
• Evaluating: considering several O(n) solutions and their trade-offs (overflow, space).

Approach 1: Brute force / HashSet Put all values in a set, then check 0..n for the one absent. Time O(n), space O(n). (Even simpler brute: for each i in 0..n linear-search the array -> O(n^2).)

Approach 2: Gauss sum Expected sum n(n+1)/2 minus the actual sum. Time O(n), space O(1). Use long to be safe against overflow.

Approach 3: XOR (final)

• Intuition: XOR is its own inverse. XOR together all indices 0..n and all array values; every number present appears twice and cancels, leaving the missing one. Start with x = n (the extra index not covered by the loop 0..n-1), then XOR i ^ a[i] for each i.
• Dry run [3,0,1], n=3: x=3; i=0: 3^0^3=0; i=1: 0^1^0=1; i=2: 1^2^1=2. Answer 2.

Java code

import java.util.*;

class MissingNumber {
    // Brute force: HashSet, O(n) time, O(n) space
    static int missingBrute(int[] a) {
        Set<Integer> s = new HashSet<>();
        for (int x : a) s.add(x);
        for (int i = 0; i <= a.length; i++)
            if (!s.contains(i)) return i;
        return -1; // unreachable when the input is valid
    }

    // Gauss sum: O(n) time, O(1) space (long avoids overflow of n(n+1)/2)
    static int missingSum(int[] a) {
        long n = a.length, expected = n * (n + 1) / 2, sum = 0;
        for (int x : a) sum += x;
        return (int) (expected - sum);
    }

    // XOR: O(n) time, O(1) space, no overflow possible
    static int missingNumber(int[] a) {
        int x = a.length;                 // the index n has no matching slot in the loop
        for (int i = 0; i < a.length; i++)
            x ^= i ^ a[i];                // present values cancel with their indices
        return x;
    }
}

Complexity

• HashSet: Time O(n), Space O(n).
• Gauss sum: Time O(n), Space O(1).
• XOR: Time O(n) (single pass), Space O(1).

Edge cases / pitfalls

• Missing value is n itself ([0,1] -> 2) or 0 ([1] -> 0). Single element [0] -> 1.
• Do not forget the initial x = n in the XOR version.
• Sum overflow for very large n in int; mention long. Sorted-input follow-up: binary search for the first index with a[i] != i.

Pattern & related problems XOR cancellation / arithmetic series. Related: #136 Single Number, #287 Find the Duplicate Number, #448 Find All Numbers Disappeared in an Array, #41 First Missing Positive, #645 Set Mismatch.

5. Reverse Bits

(Easy · LeetCode #190)

Problem statement Reverse the bits of a 32-bit unsigned integer and return the result.

• n = 00000010100101000001111010011100 (43261596) -> 00111001011110000010100101000000 (964176192)
• n = 11111111111111111111111111111101 -> 10111111111111111111111111111111
• Constraint: input is a 32-bit value. Follow-up: if called many times, how would you optimize?

How the interviewer asks / follow-ups

• Disguised: "Convert between bit orderings (MSB-first vs LSB-first) in a protocol bitmap or a checksum/CRC routine"; "reverse the bit-mask of terminal capabilities".
• Follow-ups: called many times -> cache byte reversals in a 256-entry table and combine 4 lookups, or use the divide-and-conquer mask swap (constant ops, no loop); do it without a loop; reverse only the lowest k bits; Java's Integer.reverse does the mask-swap internally; unsigned handling (use >>>; return value printed with Integer.toUnsignedString).
• Evaluating: bit shifting fluency and signed/unsigned care in Java.

Approach 1: Brute force (build a string) Convert to a 32-char binary string, reverse it, parse it back with Integer.parseUnsignedInt(s, 2). Time O(32), space O(32). Works but is clumsy; mention it and move on.

Approach 2: Shift-out / shift-in loop

• Intuition: repeat 32 times: shift res left by one, append the lowest bit of n, shift n right (logically). The first bit read (LSB of n) ends up as the MSB of res after 32 shifts.
• Dry run (4-bit analogy) n = 0010: read LSBs 0,1,0,0 in turn, so res = 0 -> 01 -> 010 -> 0100. The set bit moved from position 1 to position 2 (= 3 - 1), i.e. reversed.

Approach 3: Divide and conquer with masks (O(1), no loop) Swap the 16-bit halves, then swap adjacent bytes in each half, then nibbles, then 2-bit pairs, then single bits. Five fixed steps.

Java code

class ReverseBits {
    // Loop: 32 iterations, O(1) time (fixed width), O(1) space
    static int reverseBitsLoop(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res = (res << 1) | (n & 1);  // append lowest bit of n
            n >>>= 1;                    // logical shift: sign bit must not be replicated
        }
        return res;                      // may be negative as a signed int; the bit pattern is right
    }

    // Divide and conquer: 5 steps, no loop (good when called many times)
    static int reverseBits(int n) {
        n = (n >>> 16) | (n << 16);                                   // swap 16-bit halves
        n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);       // swap bytes
        n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);       // swap nibbles
        n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);       // swap bit pairs
        n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);       // swap adjacent bits
        return n;
    }
}

Both match Integer.reverse on 100k random ints and the two LeetCode examples (reverseBits(43261596) == 964176192).

Complexity

• Loop: Time O(32) = O(1), Space O(1).
• Mask swaps: Time O(log w) = 5 steps, O(1), Space O(1).
• String brute force: Time O(32), Space O(32).

Edge cases / pitfalls

• Use >>>= not >>=: with >>= a negative input shifts in copies of the sign bit, so the low bits read in later iterations are wrong.
• Always run exactly 32 iterations (not while (n != 0)), otherwise trailing zeros of the input are lost (reverseBits(1) must be 0x80000000, i.e. Integer.MIN_VALUE).
• Hex literals like 0xff00ff00 are negative ints in Java - that is fine, only the bit pattern matters.
• The returned int may print as negative; use Integer.toUnsignedString to show the unsigned value.

Pattern & related problems Bit-by-bit construction; divide-and-conquer bit tricks. Related: #191 Number of 1 Bits, #7 Reverse Integer (decimal), #190 with byte-cache follow-up, #89 Gray Code, #1318 Minimum Flips to Make a OR b Equal to c.