program FindNthSetBit64;
{$mode objfpc}{$H+}
(*
countTrailingZeros:
-------------------
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 and (-x)
- Its index is BsrQWord(lowestBit)
*)
function countTrailingZeros(x: QWord): LongInt;
var
lowest: QWord;
begin
lowest := x and (QWord(-x)); // isolate lowest set bit
Result := BsrQWord(lowest); // index of that bit (0–63)
end;
(*
findNthSetBit64:
----------------
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 countTrailingZeros(x) to locate the lowest set bit.
- Remove that bit using x := x and (x - 1).
- When we reach the Nth one, return 1 shl index.
*)
function findNthSetBit64(x: QWord; n: LongWord): QWord;
var
index: LongInt;
begin
while x <> 0 do
begin
index := countTrailingZeros(x);
Dec(n);
if n = 0 then
Exit(QWord(1) shl index);
x := x and (x - 1); // remove lowest set bit
end;
Result := 0; // fewer than n set bits
end;
(*
toBinary64:
-----------
Convert a 64-bit integer to a padded 64-bit binary string.
*)
function toBinary64(x: QWord): String;
var
i: Integer;
begin
Result := '';
for i := 63 downto 0 do
if (x shr i) and 1 = 1 then
Result += '1'
else
Result += '0';
end;
(*
Main
*)
var
value: QWord;
n: LongWord;
result: QWord;
begin
value :=
%0000000000000000000010000000000000001101001101101100100010100000;
n := 4;
result := findNthSetBit64(value, n);
WriteLn('Input value: ', toBinary64(value));
WriteLn('N = ', n);
WriteLn('Result mask: ', toBinary64(result));
end.
(*
run:
Input value: 0000000000000000000010000000000000001101001101101100100010100000
N = 4
Result mask: 0000000000000000000000000000000000000000000000000100000000000000
*)
