Find nth smallest integer with k one bits

impl Solution {
  pub fn nth_smallest(n: i64, k: i32) -> i64 {
    let k = k as i64;
    // Binary search on the answer. For a value v, count how many numbers in [1, v] have exactly k ones.
    // C(bits, k) combinatorics approach.

    // Count of numbers in [1, v] with exactly k ones in binary
    fn count_up_to(v: i64, k: i64) -> i64 {
      if v <= 0 || k < 0 { return 0; }
      if k == 0 { return 1; } // only 0 has 0 ones, but we want [1,v], so numbers with 0 ones in [1,v] = 0... wait
      // Actually count numbers in [0, v] with exactly k ones, then subtract if 0 has k ones
      // 0 has 0 ones.
      // Standard digit DP: count numbers in [0, v] with exactly k ones.
      let bits = 50;
      let mut result = 0i64;
      let mut ones_so_far = 0i64;
      for i in (0..bits).rev() {
        if v & (1i64 << i) != 0 {
          // If we place 0 at position i, count numbers with remaining ones in lower bits
          let remaining = k - ones_so_far;
          if remaining >= 0 && remaining <= i {
            result += comb(i, remaining);
          }
          ones_so_far += 1;
        }
      }
      // Check if v itself has exactly k ones
      if ones_so_far == k {
        result += 1;
      }
      result
    }

    fn comb(n: i64, r: i64) -> i64 {
      if r < 0 || r > n { return 0; }
      if r == 0 || r == n { return 1; }
      let r = r.min(n - r);
      let mut result = 1i64;
      for i in 0..r {
        result = result * (n - i) / (i + 1);
      }
      result
    }

    // Binary search: find smallest v such that count_up_to(v, k) >= n
    let mut lo = 1i64;
    let mut hi = 1i64 << 50;
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      if count_up_to(mid, k) >= n {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    lo
  }
}