import math
"""
count_trailing_zeros:
---------------------
Returns the number of trailing zeros in a 64‑bit integer.
Equivalent to C++ std::countr_zero or GCC __builtin_ctzll.
Algorithm:
- Isolate lowest set bit: x & -x
- Its index is log2(lowest_bit)
"""
def count_trailing_zeros(x: int) -> int:
lowest = x & -x # isolate lowest set bit
return int(math.log2(lowest)) # index (0–63)
"""
find_nth_set_bit64:
-------------------
Given:
- x : a 64-bit integer
- n : which set bit to find (1-based index)
Returns:
A 64-bit mask with ONLY the Nth set bit of x turned on.
If n is larger than the number of set bits, returns 0.
Algorithm:
- Use count_trailing_zeros(x) to locate the lowest set bit.
- Remove that bit using x &= (x - 1).
- When we reach the Nth one, return 1 << index.
"""
def find_nth_set_bit64(x: int, n: int) -> int:
while x != 0:
index = count_trailing_zeros(x)
n -= 1
if n == 0:
return 1 << index
# Remove the lowest set bit
x &= (x - 1)
return 0
"""
to_binary64:
------------
Convert integer to a padded 64-bit binary string.
"""
def to_binary64(x: int) -> str:
s = bin(x)[2:] # strip "0b"
return s.zfill(64)
# --------------------
# Main
# --------------------
value = 0b0000000000000000000010000000000000001101001101101100100010100000
n = 4
result = find_nth_set_bit64(value, n)
print("Input value: ", to_binary64(value))
print("N =", n)
print("Result mask: ", to_binary64(result))
"""
run:
Input value: 0000000000000000000010000000000000001101001101101100100010100000
N = 4
Result mask: 0000000000000000000000000000000000000000000000000100000000000000
"""
