計數整數中的設定位數？

我正在嘗試使用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);

發現我的答案在這裏：Calculating Hamming weight efficiently in matlab

來源

2013-01-08 Supa

那麼問題是什麼？ – aschepler

這個問題可能是我怎麼混合使用C和matlab代碼並使它工作... –

你的問題到底是什麼？你是否想看看一個特定的數字是否是兩個冪的？你想混合Matlab和C代碼嗎？你是@ aka.nice還是@Supa？ – slayton

使用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位整數構建LUT（只有256個條目）：

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

您只需要構建一次LUT。

一旦你的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的速度是的sum的兩倍。

來源

2013-01-09 07:14:50 Shai

計數整數中的設定位數？

回答

相關問題