matlab - 整数に設定されたビット数を数えますか?

Question

x*x-1 を使用して、整数が 2 のべき乗であるかどうかを確認し、カウントしようとしています。

long count_bits(long n) {
unsigned int c;
for c = 0:n
n = n * (n - 1);  %Determines if an integer is a power of two!
c=c+1;
end

disp(c);

ここで私の答えを見つけました：Matlabで効率的にハミングの重みを計算する

Answer 1

使用bitget:

% generate a random int number
>> n = uint32( randi( intmax('uint32'), 1, 1 ) )

n = 

   3771981510

>> count = sum(bitget(n,1:32))

count = 

   18

または、パフォーマンスが気になる場合は、ルックアップ テーブル (LUT) を使用してビットをカウントできます。

8 ビット int の LUT の作成 (256 エントリのみ):

function lut = countBitsLUT()
for ii = 0:255
    lut(ii+1) = sum(bitget(uint8(ii),1:8));
end

LUT を作成する必要があるのは 1 回だけです。

LUT を取得したら、次を使用してビット数をカウントできます。

count = lut( bitand(n,255)+1 ) + ...      % how many set bits in first byte
        lut( bitand( bitshift(n,-8), 255 ) + 1 ) + ... % how many set bits in second byte
        lut( bitand( bitshift(n,-16), 255 ) + 1 ) + ... % how many set bits in third byte
        lut( bitand( bitshift(n,-24), 255 ) + 1 ); % how many set bits in fourth byte

小さな「ベンチマーク」も行いました。

lutCount = @( n ) lut( bitand(n,255)+1 ) + ...      % how many set bits in first byte
        lut( bitand( bitshift(n,-8), 255 ) + 1 ) + ... % how many set bits in second byte
        lut( bitand( bitshift(n,-16), 255 ) + 1 ) + ... % how many set bits in third byte
        lut( bitand( bitshift(n,-24), 255 ) + 1 ); % how many set bits in fourth byte

t = [ 0 0 ];
for ii=1:1000
    n = uint32( randi( intmax('uint32'), 1, 1 ) );
    tic;
    c1 = sum(bitget(n,1:32));
    t(1) = t(1) + toc;
    tic;
    c2 = lutCount( n );
    t(2) = t(2) + toc;
    assert( c1 == c2 );
end

実行時間は次のとおりです。

t = [0.0115    0.0053]

つまり、LUT は ~ の 2 倍の速さsumですbitget。