Matlab:使用稀疏结构以二进制数加和的快速方法？

Question

大多数答案仅针对已经回答的有关汉明重量的问题,但忽略了关于find稀疏性的观点.显然,通过夏嘉曦答案在这里解决了约找到一点-但我现在还无法验证它.我在这里的答案并没有利用其他答案的独创性,比如位移,但足够好的例子答案.

输入

>> mlf=sparse([],[],[],2^31+1,1);mlf(1)=10;mlf(10)=111;mlf(77)=1010;  
>> transpose(dec2bin(find(mlf)))

ans =

001
000
000
011
001
010
101

目标

1
0
0
2
1
1
2    

使用稀疏结构快速计算二进制数的1？

Answer 1

你可以通过多种方式实现这一目标.我认为最简单的是

% Example data
F = [268469248 285213696 536904704 553649152];

% Solution 1
sum(dec2bin(F)-'0',2)

并且最快(如此处所示):

% Solution 2
w = uint32(F');

p1 = uint32(1431655765);
p2 = uint32(858993459);
p3 = uint32(252645135);
p4 = uint32(16711935);
p5 = uint32(65535);

w = bitand(bitshift(w, -1), p1) + bitand(w, p1);
w = bitand(bitshift(w, -2), p2) + bitand(w, p2);
w = bitand(bitshift(w, -4), p3) + bitand(w, p3);
w = bitand(bitshift(w, -8), p4) + bitand(w, p4);
w = bitand(bitshift(w,-16), p5) + bitand(w, p5);

Answer 2

根据您的评论,您可以使用数字向量转换为二进制字符串表示dec2bin.然后你可以按照以下方式实现你想要的,我用vector [10 11 12]作为例子:

>> sum(dec2bin([10 11 12])=='1',2)

ans =

     2
     3
     2

或等效地,

>> sum(dec2bin([10 11 12])-'0',2)

对于速度,你可以避免dec2bin这样(使用modulo-2操作,灵感来自dec2bin代码):

>> sum(rem(floor(bsxfun(@times, [10 11 12].', pow2(1-N:0))),2),2)

ans =

     2
     3
     2

N您期望的最大二进制数字在哪里.