Bit Manipulation

def single_number(nums: list[int]) -> int:
    """LC 136. Single Number.

    XOR every number together. XOR is commutative and associative and
    any value XORed with itself cancels to zero, so each pair vanishes
    and only the unpaired number survives. One pass, O(n) time, O(1)
    space.
    """
    survivor = 0
    for num in nums:
        survivor ^= num  # pairs cancel to 0; the single value remains
    return survivor

// LC 136. XOR every number together in one pass: XOR is commutative and
// associative, and any value XORed with itself cancels to zero, so each pair
// vanishes and only the unpaired element survives. O(n) time, O(1) space.
int singleNumber(vector<int> nums) {
    int result = 0;
    for (int x : nums) result ^= x;
    return result;
}

/// LC 136. XOR every number together: XOR is commutative and associative and
/// x ^ x = 0, so each pair cancels and only the unpaired element survives.
/// One pass, O(1) extra space.
pub fn single_number(nums: Vec<i32>) -> i32 {
    nums.into_iter().fold(0, |acc, x| acc ^ x)
}

/** LC 136. XOR everything: pairs cancel to 0 (x ^ x = 0, order irrelevant), leaving the unpaired value. */
export function singleNumber(nums: number[]): number {
  let acc = 0;
  for (const num of nums) {
    acc ^= num;
  }
  return acc;
}

// LC 136. XOR every number together: pairs cancel to zero, so only the
// unpaired element survives. One pass, O(1) space.
func singleNumber(nums []int) int {
	result := 0
	for _, x := range nums {
		result ^= x
	}
	return result
}

// LC 136. XOR everything in one pass: pairs cancel to zero, so only the
// unpaired value survives.
func singleNumber(_ nums: [Int]) -> Int {
    var result = 0
    for x in nums { result ^= x }
    return result
}

def hamming_weight(n: int) -> int:
    """LC 191. Number of 1 Bits.

    Loop applying n &= n - 1 until n is zero, counting iterations.
    Subtracting 1 flips the lowest set bit to 0 and the zeros below it
    to 1s, so AND-ing with the original clears EXACTLY the lowest set
    bit -- the loop runs once per set bit, not once per bit position.
    O(set bits) time, O(1) space.
    """
    set_bits = 0
    while n:
        n &= n - 1  # clears exactly the lowest set bit
        set_bits += 1
    return set_bits

// LC 191. Loop n = n & (n - 1) until n is zero, counting iterations. The
// identity: subtracting one flips the lowest set bit and everything below it,
// so the AND clears exactly that lowest set bit. The loop therefore runs once
// per SET bit rather than once per bit position.
int hammingWeight(uint32_t n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1;  // clears the lowest set bit
        ++count;
    }
    return count;
}

/// LC 191. n & (n - 1) clears exactly the lowest set bit, so counting
/// iterations until n hits zero runs once per SET bit, not once per bit
/// position. LeetCode's Rust signature passes the value as u32.
pub fn hamming_weight(n: u32) -> i32 {
    let mut n = n;
    let mut count = 0;
    while n != 0 {
        n &= n - 1;
        count += 1;
    }
    count
}

/** LC 191. n & (n-1) clears exactly the lowest set bit, so loop once per SET bit, not per position. */
export function hammingWeight(n: number): number {
  // JS bitwise ops are SIGNED 32-bit: read the input (and each AND result)
  // back as unsigned with >>> 0, or values with bit 31 set go negative and
  // the n !== 0 termination check never fires.
  n = n >>> 0;
  let count = 0;
  while (n !== 0) {
    n = (n & (n - 1)) >>> 0; // drop the lowest set bit, stay unsigned
    count++;
  }
  return count;
}

// LC 191. n &= n-1 clears exactly the lowest set bit, so the loop runs once
// per SET bit rather than once per bit position.
func hammingWeight(n uint32) int {
	count := 0
	for n != 0 {
		n &= n - 1 // clears the lowest set bit
		count++
	}
	return count
}

// LC 191. n & (n - 1) clears exactly the lowest set bit, so the loop runs
// once per SET bit rather than once per bit position.
func hammingWeight(_ n: Int) -> Int {
    var n = n
    var count = 0
    while n != 0 {
        n &= n - 1  // clears the lowest set bit
        count += 1
    }
    return count
}

def count_bits(n: int) -> list[int]:
    """LC 338. Counting Bits.

    Fill the table in order with dp[i] = dp[i >> 1] + (i & 1): shifting
    right drops only the lowest bit, so the count for i is the
    already-computed count for i >> 1 plus that dropped bit. O(n) total
    time, O(n) space for the answer itself.
    """
    bit_counts = [0] * (n + 1)
    for i in range(1, n + 1):
        bit_counts[i] = bit_counts[i >> 1] + (i & 1)  # i >> 1 drops only the low bit
    return bit_counts

// LC 338. Fill in order with dp[i] = dp[i >> 1] + (i & 1): shifting i right
// one position drops only its lowest bit, so the popcount of i is the
// already-computed popcount of i >> 1 plus that dropped bit. O(n) total,
// no per-element bit loop.
vector<int> countBits(int n) {
    vector<int> dp(n + 1, 0);
    for (int i = 1; i <= n; ++i) dp[i] = dp[i >> 1] + (i & 1);
    return dp;
}

/// LC 338. dp[i] = dp[i >> 1] + (i & 1): shifting right drops only the lowest
/// bit, so the count for i is the already-computed count of its half plus
/// that dropped bit. Fills 0..=n in O(n) total.
pub fn count_bits(n: i32) -> Vec<i32> {
    let n = n as usize;
    let mut dp = vec![0; n + 1];
    for i in 1..=n {
        dp[i] = dp[i >> 1] + (i & 1) as i32;
    }
    dp
}

/** LC 338. dp[i] = dp[i >> 1] + (i & 1): shifting right drops only the lowest bit, so add it back. O(n). */
export function countBits(n: number): number[] {
  const dp: number[] = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    dp[i] = dp[i >> 1] + (i & 1);
  }
  return dp;
}

// LC 338. dp[i] = dp[i>>1] + (i&1): shifting right drops only the low bit, so
// each popcount reuses an already-computed smaller one. O(n) total.
func countBits(n int) []int {
	dp := make([]int, n+1)
	for i := 1; i <= n; i++ {
		dp[i] = dp[i>>1] + (i & 1)
	}
	return dp
}

// LC 338. dp[i] = dp[i >> 1] + (i & 1): shifting right drops only the lowest
// bit, so each count reuses an already-computed smaller one. O(n) total.
func countBits(_ n: Int) -> [Int] {
    var dp = [Int](repeating: 0, count: n + 1)
    for i in dp.indices.dropFirst() {
        dp[i] = dp[i >> 1] + (i & 1)  // i >> 1 drops only the low bit
    }
    return dp
}

def add_binary(a: str, b: str) -> str:
    """LC 67. Add Binary.

    Walk both strings from their last characters with a shared carry,
    summing up to three bits per step, appending sum mod 2 and carrying
    sum div 2, then reverse what was built. The loop runs while EITHER
    index remains OR the carry is nonzero, which cleanly handles
    different lengths and a final carried 1. O(len(a) + len(b)) time
    and space.
    """
    digits: list[str] = []
    i, j = len(a) - 1, len(b) - 1
    carry = 0
    while i >= 0 or j >= 0 or carry:  # carry alone can mint one more digit
        total = carry
        if i >= 0:
            total += int(a[i])
            i -= 1
        if j >= 0:
            total += int(b[j])
            j -= 1
        carry, bit = divmod(total, 2)
        digits.append(str(bit))
    return "".join(reversed(digits))  # built backwards, low bit first

// LC 67. Walk both strings from their last characters with a shared carry,
// summing up to three bits per step, appending sum % 2 and carrying sum / 2,
// then reverse once at the end. The loop condition keeps running while either
// index remains OR the carry is nonzero, which handles different lengths and
// a final carried 1 without special cases.
string addBinary(string a, string b) {
    string result;
    int i = static_cast<int>(a.size()) - 1;
    int j = static_cast<int>(b.size()) - 1;
    int carry = 0;
    while (i >= 0 || j >= 0 || carry != 0) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        result.push_back(static_cast<char>('0' + sum % 2));
        carry = sum / 2;
    }
    reverse(result.begin(), result.end());
    return result;
}

/// LC 67. Walk both byte slices from the back with a shared carry, summing up
/// to three bits per step: push sum & 1, carry sum >> 1. The loop keeps going
/// while either index remains OR the carry is nonzero, which handles unequal
/// lengths and a final carried 1 in one condition. Reverse at the end.
pub fn add_binary(a: String, b: String) -> String {
    let (a, b) = (a.as_bytes(), b.as_bytes());
    let (mut i, mut j) = (a.len() as isize - 1, b.len() as isize - 1);
    let mut carry = 0u8;
    let mut out = Vec::new();
    while i >= 0 || j >= 0 || carry != 0 {
        let mut sum = carry;
        if i >= 0 {
            sum += a[i as usize] - b'0';
            i -= 1;
        }
        if j >= 0 {
            sum += b[j as usize] - b'0';
            j -= 1;
        }
        out.push(b'0' + (sum & 1));
        carry = sum >> 1;
    }
    out.reverse();
    String::from_utf8(out).unwrap()
}

/** LC 67. Walk both strings from the back with a shared carry; loop while either index OR the carry remains. */
export function addBinary(a: string, b: string): string {
  // Pure string arithmetic: inputs can be far longer than 53 bits, where
  // Number loses exactness, and no BigInt is needed for one bit at a time.
  const out: string[] = [];
  let i = a.length - 1;
  let j = b.length - 1;
  let carry = 0;
  while (i >= 0 || j >= 0 || carry > 0) {
    let sum = carry;
    if (i >= 0) sum += a.charCodeAt(i--) - 48; // '0' is code 48
    if (j >= 0) sum += b.charCodeAt(j--) - 48;
    out.push(String(sum & 1));
    carry = sum >> 1;
  }
  return out.reverse().join(""); // the final carry already emitted the leading 1
}

// LC 67. Carry loop from the back of both strings: run while either index
// remains OR the carry is nonzero, then reverse the digits built low-first.
func addBinary(a, b string) string {
	result := []byte{}
	i, j, carry := len(a)-1, len(b)-1, 0
	for i >= 0 || j >= 0 || carry != 0 { // carry alone can mint one more digit
		sum := carry
		if i >= 0 {
			sum += int(a[i] - '0')
			i--
		}
		if j >= 0 {
			sum += int(b[j] - '0')
			j--
		}
		result = append(result, byte('0'+sum%2))
		carry = sum / 2
	}
	for lo, hi := 0, len(result)-1; lo < hi; lo, hi = lo+1, hi-1 {
		result[lo], result[hi] = result[hi], result[lo]
	}
	return string(result)
}

// LC 67. Carry loop from the back of both strings; keep going while either
// index remains OR the carry is nonzero, then reverse what was built.
func addBinary(_ a: String, _ b: String) -> String {
    let aChars = Array(a)
    let bChars = Array(b)
    var digits: [Character] = []
    var i = aChars.count - 1
    var j = bChars.count - 1
    var carry = 0
    while i >= 0 || j >= 0 || carry != 0 {  // carry alone can mint one more digit
        var sum = carry
        if i >= 0 {
            sum += aChars[i].wholeNumberValue!
            i -= 1
        }
        if j >= 0 {
            sum += bChars[j].wholeNumberValue!
            j -= 1
        }
        digits.append(sum % 2 == 1 ? "1" : "0")
        carry = sum / 2
    }
    return String(digits.reversed())  // built backwards, low bit first
}

def reverse_bits(n: int) -> int:
    """LC 190. Reverse Bits.

    Loop exactly 32 times: shift the result left, OR in the input's
    lowest bit, shift the input right. All 32 iterations must run even
    after n hits zero -- the input's leading zeros become the answer's
    trailing zeros, and skipping them misaligns everything. (Python
    ints are unbounded, so the fixed count of 32 is also what pins the
    result to a 32-bit width.) O(32) time, O(1) space.
    """
    reversed_value = 0
    for _ in range(32):  # all 32, even once n is 0: zeros still shift in
        reversed_value = (reversed_value << 1) | (n & 1)  # pop low bit into result
        n >>= 1
    return reversed_value

// LC 190. Loop exactly 32 times: shift the result left, OR in the input's
// lowest bit, shift the input right. All 32 iterations must run regardless of
// leading zeros -- those zeros become the answer's trailing zeros, and
// stopping early when n hits zero would misalign everything.
uint32_t reverseBits(uint32_t n) {
    uint32_t result = 0;
    for (int i = 0; i < 32; ++i) {
        result = (result << 1) | (n & 1);
        n >>= 1;
    }
    return result;
}

/// LC 190. Exactly 32 iterations: shift the result left, OR in the input's
/// lowest bit, shift the input right. All 32 rounds must run even after the
/// input reaches zero -- leading zeros become trailing zeros in the answer,
/// and stopping early would leave the bits misaligned.
pub fn reverse_bits(x: u32) -> u32 {
    let mut x = x;
    let mut result = 0u32;
    for _ in 0..32 {
        result = (result << 1) | (x & 1);
        x >>= 1;
    }
    result
}

/** LC 190. Exactly 32 iterations (leading zeros become trailing zeros): shift result left, OR in n's low bit. */
export function reverseBits(n: number): number {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1);
    n >>>= 1; // unsigned shift: a set bit 31 must feed in zeros, not sign-extend
  }
  // << produced a SIGNED 32-bit int, so a reversed value with bit 31 set reads
  // as negative; >>> 0 reinterprets the identical bits as unsigned, which is
  // what the problem expects.
  return result >>> 0;
}

// LC 190. Exactly 32 shifts popping the input's low bit into the result; the
// leading zeros must still run so they become the answer's trailing zeros.
func reverseBits(n uint32) uint32 {
	var result uint32
	for i := 0; i < 32; i++ { // all 32, even once n is 0: zeros still shift in
		result = (result << 1) | (n & 1)
		n >>= 1
	}
	return result
}

// LC 190. Exactly 32 shifts popping the low bit into the result -- all 32
// must run even after n hits zero, or the leading zeros misalign everything.
func reverseBits(_ n: UInt32) -> UInt32 {
    var n = n
    var result: UInt32 = 0
    for _ in 0..<32 {  // all 32, even once n is 0: zeros still shift in
        result = (result << 1) | (n & 1)
        n >>= 1
    }
    return result
}

def missing_number(nums: list[int]) -> int:
    """LC 268. Missing Number.

    XOR every array value against every index 0..n: each present
    number pairs with its matching index and cancels, leaving only the
    missing one. Seed with n itself since the loop indices stop at
    n - 1. O(n) time, O(1) space.
    """
    missing = len(nums)  # the one index (n) the enumerate below never yields
    for index, value in enumerate(nums):
        missing ^= index ^ value  # present values cancel their matching index
    return missing

// LC 268. XOR every array value together with every index 0..n. Each present
// number pairs with its matching index and cancels; the missing number is the
// only value left unpaired. Seeding the accumulator with n covers the one
// index that has no loop iteration. O(n) time, O(1) space.
int missingNumber(vector<int> nums) {
    int n = static_cast<int>(nums.size());
    int result = n;  // the index n itself has no loop iteration
    for (int i = 0; i < n; ++i) result ^= i ^ nums[i];
    return result;
}

/// LC 268. XOR every array value with every index 0..n, seeded with n itself:
/// each present number cancels against its matching index and only the
/// missing one survives. Same O(n)/O(1) as the n(n+1)/2 sum formula but with
/// no overflow concern.
pub fn missing_number(nums: Vec<i32>) -> i32 {
    let mut acc = nums.len() as i32; // the one index the loop never yields
    for (i, &x) in nums.iter().enumerate() {
        acc ^= i as i32 ^ x;
    }
    acc
}

/** LC 268. XOR all indices 0..n against all values: present numbers cancel their index, the missing one survives. */
export function missingNumber(nums: number[]): number {
  let acc = nums.length; // seed with index n, the one the loop never visits
  for (let i = 0; i < nums.length; i++) {
    acc ^= i ^ nums[i];
  }
  return acc;
}

// LC 268. XOR values against indices 0..n: each present number cancels its
// matching index, leaving the missing one. Seed with n, the index the loop
// never yields.
func missingNumber(nums []int) int {
	result := len(nums) // the index n itself has no loop iteration
	for i, v := range nums {
		result ^= i ^ v
	}
	return result
}

// LC 268. XOR values against indices 0..n: each present number cancels its
// matching index; seed with n, the one index the loop never yields.
func missingNumber(_ nums: [Int]) -> Int {
    var result = nums.count  // the index n itself has no loop iteration
    for (i, value) in nums.enumerated() {
        result ^= i ^ value  // present values cancel their matching index
    }
    return result
}

def get_sum(a: int, b: int) -> int:
    """LC 371. Sum of Two Integers.

    Add without + or -: XOR is addition without carries, AND shifted
    left one is exactly the carries; loop until the carry dies. THE
    Python trap: Python ints are unbounded, so a negative number has
    infinitely many leading 1 bits and the carry would never terminate
    -- every step must be masked to 32 bits to simulate two's-
    complement wraparound, and a result with bit 31 set must be
    translated back into a negative Python int at the end. O(32) loop
    iterations, O(1) space.
    """
    MASK = 0xFFFFFFFF  # 32 ones: forces unbounded Python ints into 32-bit words
    a &= MASK  # negative inputs become their 32-bit two's-complement pattern
    b &= MASK  # (e.g. -1 -> 0xFFFFFFFF) so the carry loop can terminate
    while b:
        partial = (a ^ b) & MASK  # XOR adds carry-free; re-mask to stay 32-bit
        carry = ((a & b) << 1) & MASK  # the << 1 can spill into bit 32; clip it off
        a, b = partial, carry
    if a >= 0x80000000:  # bit 31 set: the 32-bit word encodes a negative number
        a = ~(a ^ MASK)  # flip the low 32 bits then ~: yields a - 2**32, the true value
    return a

// LC 371. XOR adds bits without carrying while AND finds the positions that
// carry; loop with sum = a ^ b and carry = (a & b) << 1 until the carry dies.
// The work happens in unsigned: left-shifting a negative signed value (or
// shifting a carry into the sign bit) is undefined behavior in C++, whereas
// unsigned arithmetic wraps mod 2^32, which is exactly two's-complement
// addition. The final cast back to int is value-preserving on every
// two's-complement target.
int getSum(int a, int b) {
    unsigned ua = static_cast<unsigned>(a);
    unsigned ub = static_cast<unsigned>(b);
    while (ub != 0) {
        unsigned carry = (ua & ub) << 1;  // unsigned shift: no UB on negatives
        ua ^= ub;                         // bitwise sum without carries
        ub = carry;
    }
    return static_cast<int>(ua);
}

/// LC 371. Add without + or -: XOR sums each bit position without carrying,
/// AND << 1 routes the carries, repeat until the carry drains to zero. The
/// ops must be wrapping: a carry out of bit 31 has to fall off for sums like
/// -2 + 3 to terminate. C lets that signed overflow happen silently, but
/// debug-build Rust panics on overflowing signed arithmetic, so wrapping_shl
/// states the two's-complement wraparound as intended behavior.
pub fn get_sum(a: i32, b: i32) -> i32 {
    let (mut a, mut b) = (a, b);
    while b != 0 {
        let carry = (a & b).wrapping_shl(1);
        a ^= b;
        b = carry;
    }
    a
}

/** LC 371. XOR adds without carrying, AND << 1 is the carry; repeat until the carry dies. */
export function getSum(a: number, b: number): number {
  // Works natively in JS: bitwise ops already wrap to signed 32-bit two's
  // complement, so negatives need no masking (unlike Python's unbounded ints)
  // and the carry walks left until it falls off bit 31.
  while (b !== 0) {
    const carry = (a & b) << 1;
    a = a ^ b;
    b = carry;
  }
  return a;
}

// LC 371. XOR adds without carries, AND shifted left one is exactly the
// carries; loop in uint32 until the carry dies so wrap is two's complement.
func getSum(a, b int) int {
	ua, ub := uint32(a), uint32(b)
	for ub != 0 {
		carry := (ua & ub) << 1 // unsigned: wraps mod 2^32, no sign-bit traps
		ua ^= ub                // bitwise sum without carries
		ub = carry
	}
	return int(int32(ua))
}

// LC 371. XOR adds without carries, AND << 1 is exactly the carries; loop
// until the carry dies. UInt32 wraps mod 2^32, which IS two's-complement
// addition, so negatives need no special casing.
func getSum(_ a: Int, _ b: Int) -> Int {
    var ua = UInt32(bitPattern: Int32(a))
    var ub = UInt32(bitPattern: Int32(b))
    while ub != 0 {
        let carry = (ua & ub) << 1  // unsigned shift: bit 31 spill is discarded
        ua ^= ub                    // bitwise sum without carries
        ub = carry
    }
    return Int(Int32(bitPattern: ua))
}

def reverse_integer(x: int) -> int:
    """LC 7. Reverse Integer.

    Pop the last digit with divmod by 10 and push it onto the result
    with multiply-by-10-plus-digit, working on the magnitude and
    reapplying the sign at the end. The overflow guard must fire
    BEFORE the push: once the multiply has happened it is too late (in
    C it has already overflowed; in Python, with unbounded ints, the
    out-of-range value would just sail through unnoticed -- the 32-bit
    limit must be checked explicitly). O(digits) time, O(1) space.
    """
    INT_MAX = 2**31 - 1  # Python won't overflow on its own; enforce 32 bits by hand
    sign = -1 if x < 0 else 1
    x = abs(x)  # magnitude only: Python's divmod on negatives rounds the wrong way
    reversed_digits = 0
    while x:
        x, digit = divmod(x, 10)  # pop the last digit
        if reversed_digits > (INT_MAX - digit) // 10:  # guard BEFORE the push
            return 0  # the push would exceed 2**31 - 1
        reversed_digits = reversed_digits * 10 + digit  # push it onto the result
    return sign * reversed_digits

// LC 7. Pop the last digit with % 10, push it with result * 10 + digit, and
// guard BEFORE the push: once the multiplication has overflowed it is already
// undefined behavior, so checking afterward is too late. result > INT_MAX/10
// means the multiply alone overflows; result == INT_MAX/10 (214748364)
// overflows only when the incoming digit exceeds INT_MAX % 10 == 7. The
// mirrored INT_MIN checks handle negatives, since C++ division and modulo
// truncate toward zero and keep x's sign on the popped digit. No 64-bit
// shortcut: the whole point is staying inside 32 bits.
int reverseInteger(int x) {
    int result = 0;
    while (x != 0) {
        int digit = x % 10;  // carries the sign of x
        x /= 10;
        if (result > INT_MAX / 10 || (result == INT_MAX / 10 && digit > INT_MAX % 10)) return 0;
        if (result < INT_MIN / 10 || (result == INT_MIN / 10 && digit < INT_MIN % 10)) return 0;
        result = result * 10 + digit;
    }
    return result;
}

/// LC 7. Pop the last digit with % 10, push it with rev * 10 + digit, shrink
/// x with / 10. The overflow guard must run BEFORE the push -- after the
/// multiply it is already too late -- comparing rev against i32::MAX / 10 and
/// i32::MIN / 10, with the boundary digit checked against MAX % 10 / MIN % 10
/// when rev sits exactly on the threshold. Return 0 on overflow.
pub fn reverse_integer(x: i32) -> i32 {
    let mut x = x;
    let mut rev: i32 = 0;
    while x != 0 {
        let digit = x % 10; // keeps the sign of x in Rust
        x /= 10;
        if rev > i32::MAX / 10 || (rev == i32::MAX / 10 && digit > i32::MAX % 10) {
            return 0;
        }
        if rev < i32::MIN / 10 || (rev == i32::MIN / 10 && digit < i32::MIN % 10) {
            return 0;
        }
        rev = rev * 10 + digit;
    }
    rev
}

/** LC 7. Pop digits with % 10, push with * 10; check the 2^31 bounds BEFORE the push, after is too late. */
export function reverseInteger(x: number): number {
  const INT_MAX = 2147483647; // 2^31 - 1
  const INT_MIN = -2147483648; // -2^31
  const MAX_PREFIX = Math.trunc(INT_MAX / 10); // 214748364
  const MIN_PREFIX = Math.trunc(INT_MIN / 10); // -214748364
  let result = 0;
  while (x !== 0) {
    const digit = x % 10; // JS % keeps the dividend's sign, so negatives pop negative digits
    x = Math.trunc(x / 10); // trunc, not floor: floor would round negatives the wrong way
    // Guard BEFORE the push. JS doubles would hold result * 10 + digit just
    // fine, so unlike C++ nothing crashes, but the problem forbids leaving
    // 32 bits and the comparison is only meaningful pre-multiplication.
    if (result > MAX_PREFIX || (result === MAX_PREFIX && digit > INT_MAX % 10)) return 0;
    if (result < MIN_PREFIX || (result === MIN_PREFIX && digit < INT_MIN % 10)) return 0;
    result = result * 10 + digit;
  }
  return result;
}

// LC 7. Pop digits with %10, push with *10+digit, guarding the 32-bit limits
// BEFORE the push; Go's / and % truncate toward zero, keeping x's sign on the
// popped digit just like C.
func reverseInteger(x int) int {
	result := 0
	for x != 0 {
		digit := x % 10 // carries the sign of x
		x /= 10
		if result > math.MaxInt32/10 || (result == math.MaxInt32/10 && digit > math.MaxInt32%10) {
			return 0
		}
		if result < math.MinInt32/10 || (result == math.MinInt32/10 && digit < math.MinInt32%10) {
			return 0
		}
		result = result*10 + digit
	}
	return result
}

// LC 7. Pop digits with % 10, push with * 10 + digit, and guard against the
// 32-bit limits BEFORE the push -- after the multiply it is already too late.
func reverseInteger(_ x: Int) -> Int {
    let intMax = Int(Int32.max)
    let intMin = Int(Int32.min)
    var x = x
    var result = 0
    while x != 0 {
        let digit = x % 10  // carries the sign of x, as in C
        x /= 10
        if result > intMax / 10 || (result == intMax / 10 && digit > intMax % 10) { return 0 }
        if result < intMin / 10 || (result == intMin / 10 && digit < intMin % 10) { return 0 }
        result = result * 10 + digit
    }
    return result
}

def range_bitwise_and(left: int, right: int) -> int:
    """LC 201. Bitwise AND of Numbers Range.

    Shift both endpoints right together, counting shifts, until they
    are equal, then shift the shared value back left by the count. The
    AND of the whole range is the common high-bit prefix: below the
    first bit where left and right disagree, every position takes both
    0 and 1 somewhere in the range and gets ANDed away. O(32) time,
    O(1) space.
    """
    shifts = 0
    while left != right:
        left >>= 1  # strip low bits until only the shared prefix remains
        right >>= 1
        shifts += 1
    return left << shifts  # the common prefix, zero-padded back to position

// LC 201. Shift both endpoints right together, counting shifts, until they
// are equal, then shift that shared value back left. Every bit below the
// first position where left and right disagree takes both values 0 and 1
// somewhere in the range and is ANDed away, so the answer is exactly the
// common high-bit prefix. O(32) time.
int rangeBitwiseAnd(int left, int right) {
    int shift = 0;
    while (left != right) {  // strip low bits until only the shared prefix remains
        left >>= 1;
        right >>= 1;
        ++shift;
    }
    return left << shift;
}

/// LC 201. Shift both endpoints right together, counting shifts, until they
/// are equal, then shift the shared value back left. The AND of the whole
/// range is the common high-bit prefix: below the first disagreeing bit,
/// every position takes both 0 and 1 somewhere in the range and gets ANDed
/// away.
pub fn range_bitwise_and(left: i32, right: i32) -> i32 {
    let (mut left, mut right) = (left, right);
    let mut shifts = 0;
    while left != right {
        left >>= 1;
        right >>= 1;
        shifts += 1;
    }
    left << shifts
}

/** LC 201. Shift both ends right until equal, then shift back: only the common high prefix survives the AND. */
export function rangeBitwiseAnd(left: number, right: number): number {
  let shift = 0;
  while (left !== right) {
    // below the first disagreeing bit, every position takes both 0 and 1
    // somewhere in the range, so the AND zeroes it out
    left >>>= 1; // >>> for safety, though constraints keep bit 31 clear
    right >>>= 1;
    shift++;
  }
  return left << shift; // never re-sets bit 31: inputs are at most 2^31 - 1
}

// LC 201. Shift both endpoints right until they agree, then shift back: the
// AND of the whole range is exactly the common high-bit prefix.
func rangeBitwiseAnd(left, right int) int {
	shift := 0
	for left != right { // strip low bits until only the shared prefix remains
		left >>= 1
		right >>= 1
		shift++
	}
	return left << shift
}

// LC 201. Shift both endpoints right together until they are equal, then
// shift back: the AND of the whole range is the common high-bit prefix.
func rangeBitwiseAnd(_ left: Int, _ right: Int) -> Int {
    var left = left
    var right = right
    var shift = 0
    while left != right {  // strip low bits until only the shared prefix remains
        left >>= 1
        right >>= 1
        shift += 1
    }
    return left << shift  // the common prefix, zero-padded back to position
}

def min_end(n: int, x: int) -> int:
    """LC 3133. Minimum Array End.

    Every element of the array must contain all of x's set bits (the
    AND equals x), so the candidates are exactly x with extra bits
    placed in x's ZERO positions -- and the k-th smallest candidate
    writes k's binary digits into those gaps, lowest gap first. The
    first element can be x itself (k = 0), so the n-th element is x
    with the bits of n - 1 spread into its zero positions. O(64) time,
    O(1) space.
    """
    fill = n - 1  # x itself is element 0, so the last element writes n-1 into the gaps
    result = x
    position = 1  # write cursor, one bit at a time from the low end
    while fill:
        if x & position == 0:  # a zero position in x: the next free gap
            if fill & 1:
                result |= position  # drop the lowest unplaced bit of n-1 here
            fill >>= 1  # that bit of n-1 is now placed; line up the next one
        position <<= 1  # advance the cursor whether or not this spot was free
    return result

// LC 3133. Every element of the array must contain all of x's set bits (the
// AND of the array equals x), so the candidates are exactly x with extra bits
// placed in x's ZERO positions, and writing the value k into those gap
// positions yields the (k+1)-th smallest candidate. The minimal last element
// of an n-long strictly increasing array is therefore x with the bits of
// n - 1 spread, lowest first, into x's zero positions. long long throughout:
// with n, x up to 10^8 the filled value can exceed 32 bits.
long long minEnd(int n, int x) {
    long long result = x;
    long long k = n - 1;  // bits of k fill x's zero positions, lowest first
    for (long long bit = 1; k != 0; bit <<= 1) {
        if ((result & bit) == 0) {          // a zero position of x
            if (k & 1) result |= bit;       // deposit k's lowest remaining bit
            k >>= 1;
        }
    }
    return result;
}

/// LC 3133. Every element of the array must keep all of x's set bits, so the
/// candidates are x with extra bits written into x's ZERO positions, and the
/// kth smallest writes k into those gaps lowest-first. The answer is x with
/// the bits of n - 1 spread into its zero positions, in i64 because the
/// spread can push past 32 bits.
pub fn min_end(n: i32, x: i32) -> i64 {
    let mut result = x as i64;
    let mut k = (n - 1) as i64;
    let mut bit = 0;
    while k != 0 {
        if result & (1 << bit) == 0 {
            result |= (k & 1) << bit;
            k >>= 1;
        }
        bit += 1;
    }
    result
}

/** LC 3133. Every element needs all of x's bits, so the k-th candidate writes k into x's ZERO bit positions; the answer spreads n-1, lowest bit first. */
export function minEnd(n: number, x: number): number {
  // BigInt is mandatory here: x can occupy ~27 low bits, pushing the spread
  // bits of n-1 up toward bit 55. Number bitwise ops truncate to signed
  // 32 bits (1 << 32 wraps to 1), and past 2^53 Number cannot even represent
  // every integer, so the shifts and ORs must run in BigInt.
  let result = BigInt(x);
  let remaining = BigInt(n - 1); // 0-indexed rank of the largest element
  let bit = 0n;
  while (remaining > 0n) {
    if (((result >> bit) & 1n) === 0n) {
      result |= (remaining & 1n) << bit; // fill x's zero slots lowest-first
      remaining >>= 1n;
    }
    bit++;
  }
  return Number(result); // LeetCode's signature wants number; convert only at the very end
}

// LC 3133. Every element must contain x's set bits, so write the bits of n-1
// into x's ZERO positions, lowest gap first; int64 since it can pass 32 bits.
func minEnd(n, x int) int64 {
	result := int64(x)
	k := int64(n - 1) // bits of k fill x's zero positions, lowest first
	for bit := int64(1); k != 0; bit <<= 1 {
		if result&bit == 0 { // a zero position of x
			if k&1 == 1 {
				result |= bit // deposit k's lowest remaining bit
			}
			k >>= 1
		}
	}
	return result
}

// LC 3133. Every element must contain x's set bits (the AND equals x), so the
// minimal n-th element writes the bits of n - 1 into x's ZERO positions,
// lowest gap first.
func minEnd(_ n: Int, _ x: Int) -> Int {
    var result = x
    var k = n - 1  // x itself is element 0, so the last element fills with n-1
    var bit = 1    // write cursor, one bit at a time from the low end
    while k != 0 {
        if result & bit == 0 {  // a zero position of x: the next free gap
            if k & 1 == 1 { result |= bit }  // deposit k's lowest remaining bit
            k >>= 1
        }
        bit <<= 1  // advance the cursor whether or not this spot was free
    }
    return result
}