# Bit Manipulation — Part 2: Interview Problems

Six problems on XOR cancellation, bit counting, bit DP, unsigned reversal and addition from logic gates.

## 1. Single Number (LeetCode 136)

**🟢 Easy.** Every element appears twice except one. Find it in O(n) time and O(1) space.

```text
[4,1,2,1,2] → 4
```

**Approach.** XOR all numbers: pairs cancel (`x ^ x = 0`) and XOR is commutative and associative, so only the single number remains.

**Complexity.** O(n) time, O(1) space.

```typescript
function singleNumber(nums: number[]): number {
  return nums.reduce((acc, x) => acc ^ x, 0);
}
```

```python
def single_number(nums):
    result = 0
    for x in nums:
        result ^= x
    return result
```

## 2. Number of 1 Bits (LeetCode 191)

**🟢 Easy.** Return the number of set bits in the binary representation of a non-negative integer.

```text
11 = 1011₂ → 3
```

**Approach.** Repeatedly drop the lowest set bit with `n &= n − 1` and count iterations: the loop runs once per set bit, not once per bit position.

**Complexity.** O(number of set bits) time.

```typescript
function hammingWeight(n: number): number {
  let count = 0;
  n = n >>> 0;                 // treat as unsigned 32-bit
  while (n) { n = (n & (n - 1)) >>> 0; count++; }
  return count;
}
```

```python
def hamming_weight(n):
    count = 0
    while n:
        n &= n - 1          # drop the lowest set bit
        count += 1
    return count
```

## 3. Counting Bits (LeetCode 338)

**🟢 Easy.** Return an array `ans` where `ans[i]` is the number of 1 bits in i, for 0 ≤ i ≤ n, in O(n).

```text
n = 5 → [0,1,1,2,1,2]
```

**Approach.** DP on bits: `i >> 1` drops the last bit, which is `i & 1`, so `bits[i] = bits[i >> 1] + (i & 1)`.

**Complexity.** O(n) time.

```typescript
function countBits(n: number): number[] {
  const bits = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) bits[i] = bits[i >> 1] + (i & 1);
  return bits;
}
```

```python
def count_bits(n):
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        bits[i] = bits[i >> 1] + (i & 1)
    return bits
```

## 4. Missing Number (LeetCode 268)

**🟢 Easy.** `nums` contains n distinct numbers from `0..n`. Return the missing one.

```text
[3,0,1] → 2
```

**Approach.** XOR every index 0..n with every value: each present number cancels with its index, leaving the missing one. (The sum formula `n(n+1)/2 − sum` also works; XOR avoids overflow in fixed-width languages.)

**Complexity.** O(n) time, O(1) space.

```typescript
function missingNumber(nums: number[]): number {
  let result = nums.length;
  nums.forEach((x, i) => { result ^= i ^ x; });
  return result;
}
```

```python
def missing_number(nums):
    result = len(nums)
    for i, x in enumerate(nums):
        result ^= i ^ x
    return result
```

## 5. Reverse Bits (LeetCode 190)

**🟢 Easy.** Reverse the bits of a 32-bit unsigned integer.

```text
00000010100101000001111010011100 → 00111001011110000010100101000000
```

**Approach.** 32 times: shift the result left, append the input's lowest bit, shift the input right. In JavaScript, finish with `>>> 0` so the result is read as unsigned; in Python, results stay within 32 bits because you only append 32 bits.

**Complexity.** O(32) time.

```typescript
function reverseBits(n: number): number {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result = ((result << 1) | (n & 1)) >>> 0;
    n >>>= 1;
  }
  return result;
}
```

```python
def reverse_bits(n):
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result
```

## 6. Sum of Two Integers (LeetCode 371)

**🟠 Medium.** Return `a + b` without using `+` or `−`.

```text
a = 2, b = 3 → 5
```

**Approach.** XOR adds without carries; `(a & b) << 1` computes the carries. Repeat until there are no carries. In Python, integers are unbounded, so mask to 32 bits on every step and convert back to a signed value at the end; in JS/TS, the `| 0` semantics of bitwise ops already work in 32 bits.

**Complexity.** O(32) iterations.

```typescript
function getSum(a: number, b: number): number {
  while (b !== 0) {
    const carry = (a & b) << 1;
    a = a ^ b;
    b = carry;
  }
  return a;
}
```

```python
def get_sum(a, b):
    MASK, MAX = 0xFFFFFFFF, 0x7FFFFFFF
    while b & MASK:
        a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK
    a &= MASK
    return a if a <= MAX else ~(a ^ MASK)   # back to signed 32-bit
```