Bit Manipulation

123.45 (base 10) = 1*10^2 + 2*10^1 + 3*10^0 + 4*10^-1 + 5*10^-2
 720.5 (base 8)  = 7*8^2  + 2*8^1  + 0*8^0  + 5*8^-1
  1011 (base 2)  = 1*2^3  + 0*2^2  + 1*2^1  + 1*2^0    = 8 + 0 + 2 + 1 = 11

1011 1101  ->  B    D  ->  0xBD  =  11*16 + 13  =  189
                           each nibble maps to one hex digit — no arithmetic needed

0xFFFFFFFF = 32 ones       0x7FFFFFFF = 31 ones = Integer.MAX_VALUE

(traces are 8-bit for space; a real int is the same picture, 32 wide)

 5  = 0000 0101
~5  = 1111 1010     flip every bit
-5  = 1111 1011     ... + 1

check:  5 + (-5) = 1 0000 0000  ->  the carry falls out of the box, leaving 0 ✓

x       = 0101 1000        lowest set bit is bit 3
x - 1   = 0101 0111        borrowing flips that 1 to 0, and every 0 below it to 1
-x      = 1010 1000        = ~x + 1

               above bit 3     at bit 3    below bit 3
  x vs x-1  :  identical       1 vs 0      complementary
  x vs -x   :  complementary   1 vs 1      both 0

x & (x-1) = 0101 0000      above survives; bit 3 and everything under it AND to 0
x & (-x)  = 0000 1000      above ANDs to 0; only bit 3 survives

-8 >> 1  = -4            1111 1000 -> 1111 1100    sign preserved
-8 >>> 1 = 2147483644    1111 1000 -> 0111 1100    sign bit treated as just another bit

# python
MASK    = 0xFFFFFFFF        # keep only the low 32 bits
INT_MAX = 0x7FFFFFFF        # 2^31 - 1

def to_signed(x):
    """read a masked 32-bit pattern back as a signed Python int"""
    return x if x <= INT_MAX else ~(x ^ MASK)

~   ->   * / %   ->   + -   ->   << >>   ->   &   ->   ^   ->   |

x << 1 + 2        parses as  x << (1 + 2)     -> x << 3, not (x << 1) + 2
a ^ b + 1         parses as  a ^ (b + 1)

x = 0b101000  (= 40)

Integer.highestOneBit(x)             = 0b100000 = 32     <- a VALUE
Integer.lowestOneBit(x)              = 0b001000 = 8      <- a VALUE  (exactly x & -x)
Integer.numberOfTrailingZeros(x)     = 3                 <- an INDEX
31 - Integer.numberOfLeadingZeros(x) = 5                 <- an INDEX

                        x = -19      Java            Python
popcount                             30              3        <- DIVERGES (Java counts the sign bits)
lowest set bit (value)               1               1        <- agrees
lowest set bit (index)               0               0        <- agrees
highest set bit (value)              -2147483648     16       <- DIVERGES (Java: always the sign bit)
highest set bit (index)              31              4        <- DIVERGES (Java: always 31)

value helpers  ->  Integer.highestOneBit(0)         = 0
                   Integer.lowestOneBit(0)          = 0

raw counts     ->  Integer.numberOfTrailingZeros(0) = 32     <- a count, not a position
                   Integer.numberOfLeadingZeros(0)  = 32

derived index  ->  31 - Integer.numberOfLeadingZeros(0)      = -1
                   (0).bit_length() - 1        (Python)      = -1

# python
# IDEA: floor(log2 x) == x.bit_length() - 1, exactly, for every x > 0
x = (1 << 53) - 1
x.bit_length() - 1        # 52  <- correct
int(math.log2(x))         # 53  <- WRONG: log2 rounded up to 53.0

x = (1 << 64) - 1
x.bit_length() - 1        # 63  <- correct
int(math.log2(x))         # 64  <- WRONG

pre[0]   = 0
pre[i+1] = pre[i] ^ a[i]

a[l] ^ a[l+1] ^ ... ^ a[r]  =  pre[r+1] ^ pre[l]

# python
# IDEA: pre[i+1] = XOR of a[0..i]; any range XOR is then one operation
# time = O(n) build + O(1) per query, space = O(n)
def build(a):
    pre = [0] * (len(a) + 1)
    for i, v in enumerate(a):
        pre[i + 1] = pre[i] ^ v
    return pre

def range_xor(pre, l, r):        # inclusive [l, r]
    return pre[r + 1] ^ pre[l]

4k   = ...00
4k+1 = ...01     (4k) ^ (4k+1)   = 1   <- differ only in bit 0
4k+2 = ...10
4k+3 = ...11     (4k+2) ^ (4k+3) = 1   <- differ only in bit 0

                 1 ^ 1 = 0             <- so each aligned quadruple vanishes

# python
# IDEA: aligned blocks of 4 cancel; only n % 4 decides what is left
# time = O(1), space = O(1)
def xor_to(n):                   # XOR of 0..n  (identical to 1..n, since 0 changes nothing)
    return [n, 1, n + 1, 0][n % 4]

def xor_range(l, r):             # XOR of l..r
    return xor_to(r) ^ xor_to(l - 1)

// java
// IDEA: swap without a temporary. Correct ONLY when the two operands are distinct.
a ^= b;  b ^= a;  a ^= b;

swap(arr, i, j) with i == j, arr[i] = 7

arr[i] ^= arr[j]   ->  7 ^ 7 = 0     both names point at the same slot
arr[j] ^= arr[i]   ->  0 ^ 0 = 0
arr[i] ^= arr[j]   ->  0 ^ 0 = 0     the 7 is gone

// java
int  testBit(int x, int i)  { return (x >> i) & 1; }   // 1 if bit i is set, else 0
int  setBit(int x, int i)   { return x | (1 << i); }   // force bit i to 1
int  clearBit(int x, int i) { return x & ~(1 << i); }  // force bit i to 0
int  toggleBit(int x, int i){ return x ^ (1 << i); }   // flip bit i
int  lowestSetBit(int x)    { return x & -x; }         // isolate lowest 1-bit
int  clearLowestBit(int x)  { return x & (x - 1); }    // turn OFF lowest 1-bit

# python
def test_bit(x, i):    return (x >> i) & 1     # 1 if bit i is set, else 0
def set_bit(x, i):     return x | (1 << i)     # force bit i to 1
def clear_bit(x, i):   return x & ~(1 << i)    # force bit i to 0
def toggle_bit(x, i):  return x ^ (1 << i)     # flip bit i
def lowest_set_bit(x): return x & -x           # isolate lowest 1-bit
def clear_lowest(x):   return x & (x - 1)      # turn OFF lowest 1-bit

// java
// IDEA: each `x &= (x - 1)` removes exactly one set bit
public int countBits(int x) {
    int count = 0;
    while (x != 0) {
        x &= (x - 1);   // clear lowest set bit
        count++;
    }
    return count;
    // built-in: Integer.bitCount(x)
}

# python
# IDEA: each `x &= (x - 1)` removes exactly one set bit
def count_bits(x):
    count = 0
    while x:
        x &= (x - 1)    # clear lowest set bit
        count += 1
    return count
    # built-in: bin(x).count("1")

x = 1100   x & (x-1) = 1100 & 1011 = 1000   count = 1
x = 1000   x & (x-1) = 1000 & 0111 = 0000   count = 2
x = 0000   stop                              → 2 set bits

// java
// LC 461 - Hamming Distance (the 2-number base case)
// IDEA: differing bits of x and y are exactly the set bits of x ^ y
// time = O(popcount), space = O(1)
class Solution {
    public int hammingDistance(int x, int y) {
        int diff = x ^ y, count = 0;
        while (diff != 0) {
            diff &= (diff - 1);   // clear lowest set bit
            count++;
        }
        return count;             // built-in: Integer.bitCount(x ^ y)
    }
}

// LC 477 - Total Hamming Distance (all pairs)
// IDEA: per bit column, ones * (n - ones) pairs differ there
// time = O(32 * N), space = O(1)
class Solution2 {
    public int totalHammingDistance(int[] nums) {
        int n = nums.length, total = 0;
        for (int i = 0; i < 32; i++) {
            int ones = 0;
            for (int x : nums) ones += (x >> i) & 1;   // count 1s in column i
            total += ones * (n - ones);                // each 1 pairs with each 0
        }
        return total;
    }
}

# python
# LC 461 - Hamming Distance
# time = O(popcount), space = O(1)
class Solution(object):
    def hammingDistance(self, x, y):
        diff, count = x ^ y, 0
        while diff:
            diff &= diff - 1          # clear lowest set bit
            count += 1
        return count                  # built-in: bin(x ^ y).count("1")


# LC 477 - Total Hamming Distance
# IDEA: per bit column, ones * (n - ones) pairs differ there
# time = O(32 * N), space = O(1)
class Solution2(object):
    def totalHammingDistance(self, nums):
        n, total = len(nums), 0
        for i in range(32):
            ones = sum((x >> i) & 1 for x in nums)   # count 1s in column i
            total += ones * (n - ones)
        return total

bit column :  0     1     2     3
ones       :  0     2     2     1        n = 3
zeros      :  3     1     1     2
pairs      : 0*3   2*1   2*1   1*2  ->  0 + 2 + 2 + 2 = 6

// java
// LC 318 - Maximum Product of Word Lengths
// IDEA: encode each word's letters as a 26-bit mask; two words share no letter iff (mA & mB) == 0
// time = O(N * L + N^2), space = O(N)
class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        int[] mask = new int[n];
        for (int i = 0; i < n; i++) {
            for (char c : words[i].toCharArray()) {
                mask[i] |= 1 << (c - 'a');       // add letter c to the set
            }
        }
        int best = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((mask[i] & mask[j]) == 0) {  // disjoint letter sets
                    best = Math.max(best, words[i].length() * words[j].length());
                }
            }
        }
        return best;
    }
}

# python
# LC 318 - Maximum Product of Word Lengths
# IDEA: encode each word's letters as a 26-bit mask; disjoint iff (mA & mB) == 0
# time = O(N * L + N^2), space = O(N)
class Solution(object):
    def maxProduct(self, words):
        masks = []
        for w in words:
            m = 0
            for c in w:
                m |= 1 << (ord(c) - ord('a'))    # add letter c to the set
            masks.append(m)

        best = 0
        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                if masks[i] & masks[j] == 0:     # no shared letter
                    best = max(best, len(words[i]) * len(words[j]))
        return best

// java
// LC 1239 - Maximum Length of a Concatenated String with Unique Characters
// IDEA: keep every reachable "union of disjoint words" mask; answer = max popcount
// time = O(2^N * 26), space = O(2^N)
class Solution {
    public int maxLength(List<String> arr) {
        List<Integer> masks = new ArrayList<>();
        masks.add(0);                                  // empty selection
        int best = 0;
        for (String s : arr) {
            int m = 0;
            boolean dup = false;
            for (char c : s.toCharArray()) {
                int bit = 1 << (c - 'a');
                if ((m & bit) != 0) { dup = true; break; }   // word itself repeats a letter
                m |= bit;
            }
            if (dup) continue;
            // iterate BACKWARDS over the snapshot so newly added masks aren't reused this round
            for (int i = masks.size() - 1; i >= 0; i--) {
                int cur = masks.get(i);
                if ((cur & m) != 0) continue;          // overlap -> can't concatenate
                masks.add(cur | m);
                best = Math.max(best, Integer.bitCount(cur | m));
            }
        }
        return best;
    }
}

# python
# LC 1239 - Maximum Length of a Concatenated String with Unique Characters
# IDEA: keep every reachable "union of disjoint words" mask; answer = max popcount
# time = O(2^N * 26), space = O(2^N)
class Solution(object):
    def maxLength(self, arr):
        masks, best = [0], 0                 # 0 = empty selection
        for s in arr:
            m, dup = 0, False
            for c in s:
                bit = 1 << (ord(c) - ord('a'))
                if m & bit:                  # word itself repeats a letter
                    dup = True
                    break
                m |= bit
            if dup:
                continue
            for cur in list(masks):          # snapshot, so this word is used at most once
                if cur & m:                  # overlap -> can't concatenate
                    continue
                masks.append(cur | m)
                best = max(best, bin(cur | m).count("1"))
        return best

// java
// LC 187 - Repeated DNA Sequences
// IDEA: 2 bits per base -> a 10-char window is one 20-bit int; roll it with shift + mask
// time = O(N), space = O(N)
class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        int L = 10, n = s.length();
        List<String> res = new ArrayList<>();
        if (n <= L) return res;

        int mask = (1 << (2 * L)) - 1;          // keep only the low 20 bits
        int hash = 0;
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < n; i++) {
            hash = ((hash << 2) | "ACGT".indexOf(s.charAt(i))) & mask;  // push new base, drop oldest
            if (i >= L - 1) {
                int c = seen.getOrDefault(hash, 0) + 1;
                seen.put(hash, c);
                if (c == 2) res.add(s.substring(i - L + 1, i + 1));     // report once
            }
        }
        return res;
    }
}

# python
# LC 187 - Repeated DNA Sequences
# IDEA: 2 bits per base -> a 10-char window is one 20-bit int; roll it with shift + mask
# time = O(N), space = O(N)
class Solution(object):
    def findRepeatedDnaSequences(self, s):
        L, n = 10, len(s)
        if n <= L:
            return []
        code = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
        mask = (1 << (2 * L)) - 1               # keep only the low 20 bits
        h, seen, res = 0, {}, []
        for i, c in enumerate(s):
            h = ((h << 2) | code[c]) & mask     # push new base, drop the oldest
            if i >= L - 1:
                seen[h] = seen.get(h, 0) + 1
                if seen[h] == 2:                # report each repeat exactly once
                    res.append(s[i - L + 1:i + 1])
        return res

# python
mask & (1 << i)          # is item i in the subset?
mask | (1 << i)          # add item i
mask & ~(1 << i)         # remove item i
bin(mask).count("1")     # size of the subset
sub = (sub - 1) & mask   # enumerate all SUB-masks of `mask` (classic trick)

state : dp[mask][i]      mask = set of visited cities, i = current city
trans : dp[mask | (1<<j)][j] = min( dp[mask][i] + dist[i][j] )   for j not in mask
answer: min over i of dp[FULL][i] (+ dist[i][start] for a cycle)
time  : O(2^n · n^2)     space : O(2^n · n)

// java
// Held–Karp TSP skeleton: dp[mask][i] = min cost visiting `mask`, ending at city i
int tsp(int[][] dist) {
    int n = dist.length, FULL = (1 << n) - 1;
    int[][] dp = new int[1 << n][n];
    for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE / 2);
    dp[1][0] = 0;                             // start at city 0, only it visited
    for (int mask = 1; mask <= FULL; mask++) {
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0) continue;         // i must be in mask
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) != 0) continue;     // j must NOT be visited yet
                int next = mask | (1 << j);
                dp[next][j] = Math.min(dp[next][j], dp[mask][i] + dist[i][j]);
            }
        }
    }
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) ans = Math.min(ans, dp[FULL][i] + dist[i][0]); // close cycle
    return ans;
}

state : dp[mask] = how full the CURRENT bucket is, given `mask` items are already placed
        (-1 = mask unreachable)
key   : sum(mask) is fixed by the mask, so the bucket index is implied —
        every time the running bucket hits `target` it wraps to 0 and a new bucket starts
trans : dp[mask | (1<<i)] = (dp[mask] + nums[i]) % target,  allowed iff dp[mask] + nums[i] <= target
answer: dp[FULL] == 0   (all items used AND the last bucket closed exactly)
time  : O(2^n · n)      space : O(2^n)

// java
// LC 698 - Partition to K Equal Sum Subsets
// IDEA: dp[mask] = fill level of the current bucket; % target rolls over to the next bucket
// time = O(2^n * n), space = O(2^n)
class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int x : nums) sum += x;
        if (sum % k != 0) return false;                 // can't split evenly
        int target = sum / k, n = nums.length;

        Arrays.sort(nums);                              // ascending -> enables the `break` prune
        if (nums[n - 1] > target) return false;         // one item already overflows a bucket

        int FULL = (1 << n) - 1;
        int[] dp = new int[1 << n];
        Arrays.fill(dp, -1);                            // -1 = state not reachable
        dp[0] = 0;                                      // nothing placed, empty bucket

        for (int mask = 0; mask <= FULL; mask++) {
            if (dp[mask] < 0) continue;                 // unreachable
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) continue;   // item i already used
                if (dp[mask] + nums[i] > target) break; // sorted -> all later items fail too
                int next = mask | (1 << i);
                if (dp[next] < 0) {
                    dp[next] = (dp[mask] + nums[i]) % target;  // == 0 -> bucket closed, start next
                }
            }
        }
        return dp[FULL] == 0;   // every item used and the final bucket landed exactly on target
    }
}

# python
# LC 698 - Partition to K Equal Sum Subsets
# IDEA: dp[mask] = fill level of the current bucket; % target rolls over to the next bucket
# time = O(2^n * n), space = O(2^n)
class Solution(object):
    def canPartitionKSubsets(self, nums, k):
        total = sum(nums)
        if total % k:                       # can't split evenly
            return False
        target, n = total // k, len(nums)

        nums.sort()                         # ascending -> enables the `break` prune
        if nums[-1] > target:               # one item already overflows a bucket
            return False

        FULL = (1 << n) - 1
        dp = [-1] * (1 << n)                # -1 = state not reachable
        dp[0] = 0                           # nothing placed, empty bucket

        for mask in range(FULL + 1):
            if dp[mask] < 0:
                continue
            for i in range(n):
                if mask & (1 << i):         # item i already used
                    continue
                if dp[mask] + nums[i] > target:
                    break                   # sorted -> all later items fail too
                nxt = mask | (1 << i)
                if dp[nxt] < 0:
                    dp[nxt] = (dp[mask] + nums[i]) % target   # 0 -> bucket closed
        return dp[FULL] == 0

mask 0000  dp=0    place nums[0]=1 -> dp[0001] = 1
mask 0001  dp=1    place nums[3]=3 -> dp[1001] = (1+3) % 4 = 0   (bucket closed!)
mask 0011  dp=3    place nums[2]=2 -> 3+2 = 5 > 4 -> break        (dead branch)
mask 1001  dp=0    place nums[1]=2 -> dp[1011] = 2
mask 1011  dp=2    place nums[2]=2 -> dp[1111] = (2+2) % 4 = 0
                                     dp[FULL] == 0 -> TRUE  ([1,3] and [2,2])