Count binary palindromic numbers

impl Solution {
  pub fn count_binary_palindromes(n: i64) -> i32 {
    // Count binary palindromes in [0, n].
    // "0" is palindrome (1 palindrome for n >= 0).
    // For each bit-length L from 1 upward, count palindromes with exactly L bits.
    // A L-bit palindrome: msb = 1, lsb = 1, and the string is palindrome.
    // Number of free bits = ceil((L-2)/2) = (L-1)/2 (integer division, choosing upper half).
    // Actually free bits = floor((L-1)/2) values, each in {0,1}.
    // Total palindromes of length L = 2^floor((L-1)/2).
    // We sum those fully < n's bit-length, then handle the ones with same bit-length as n.

    if n == 0 { return 1; }

    let mut count = 1i32; // include 0
    let bits_n = 64 - n.leading_zeros() as usize;

    // Count palindromes of lengths 1..bits_n-1
    for len in 1..bits_n {
      let free = (len - 1) / 2;
      count += 1i32 << free;
    }

    // Count palindromes of exactly bits_n bits that are <= n
    count += Self::count_exact_len(n, bits_n);

    count
  }

  fn count_exact_len(n: i64, len: usize) -> i32 {
    // Count L-bit palindromes <= n using O(free) digit-DP.
    // A palindrome of length L is determined by its upper ceil(L/2) bits,
    // with b[0]=1 fixed. Free bits: b[1]..b[free], free = (L-1)/2.
    // Mirroring means b[L-1-i] = b[i], so the lower half mirrors the upper.
    // Key insight: if we set b[i] < n's bit at position i (from MSB) while
    // being tight above, all remaining 2^(free-i) choices yield palindromes < n
    // because bit position i is more significant than all remaining bits.
    if len == 1 { return 1; } // only "1"

    let free = (len - 1) / 2;
    let mut count = 0i32;

    // Process each free bit position from MSB to LSB
    for i in 1..=free {
      let n_bit = (n >> (len - 1 - i)) & 1;
      if n_bit == 1 {
        // Setting b[i] = 0 gives 2^(free-i) valid palindromes < n
        count += 1i32 << (free - i);
        // Continue tight with b[i] = 1
      }
      // If n_bit == 0: must stay tight with b[i] = 0
    }

    // Check the fully-tight palindrome (mirror n's upper half)
    let tight_pal = Self::build_tight_palindrome(n, free, len);
    if tight_pal <= n { count += 1; }

    count
  }

  fn build_tight_palindrome(n: i64, free: usize, len: usize) -> i64 {
    let mut bits = vec![0u8; len];
    bits[0] = 1;
    for i in 1..=free {
      bits[i] = ((n >> (len - 1 - i)) & 1) as u8;
    }
    for i in 0..len / 2 {
      bits[len - 1 - i] = bits[i];
    }
    let mut val = 0i64;
    for &b in &bits {
      val = (val << 1) | b as i64;
    }
    val
  }
}