末尾に続く0の数 Count Trailing Zeros - にゃにゃんのScrapbox

末尾に続く0の数 Count Trailing Zeros

#ビット演算で、値の末尾から続く0のビットの数を数えたい。

Count Trailing Zero #CTZ <-> #CLZ 先頭から続く0の数 Count Leading Zeros

組み込み関数を使う

code:c++

#ifdef _MSC_VER

#include <intrin.h>

#include <x86intrin.h>

#ifdef __GNUC__

__builtin_ctzll(x)

__builtin_ctz(x)

_tzcnt_u64(x)

_tzcnt_u32(x)

https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#techs=Other&text=_tzcnt_u64&ig_expand=6906

https://gcc.gnu.org/onlinedocs/gcc-4.3.3/gcc/Other-Builtins.html#Other-Builtins

ビット演算で書く

code: c++

popcount((x & -x) - 1)

popcount(~x & (x - 1))

2の補数や引き算を使って下位の0のビットを浮き上がらせている

x = 0b01110100として、(x & -x) - 1を考える

-x = 0b10001100

x & -x = 0b00000100

(x & -x) - 1 = 0b00000011

また、~x & (x - 1)は

~x = 0b10001011

x - 1 = 0b01110011

~x & (x - 1) = 0b00000011

#1のビットを数える_popcount #popcount