计数整数中的设定位数？

我正在尝试使用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

计数整数中的设定位数？

回答

相关问题