给定一个整数n,我想切换该数字的二进制表示中的所有位,从低到高.为此,我执行以下操作[bit_string是一个包含1和0的字符串,是n的二进制表示]
for i in range(lower,upper+1):
n ^= (1 << len(bit_string)-1-i) #Toggle the ith bit
然后,我还需要确定给定一个范围,比如从低到高,设置了多少位.我的代码如下:
number_of_ones = 0
for i in range(lower,upper+1):
if(n & (1 << len(bit_string)-1-i)): #Check the ith bit
number_of_ones+=1
但是,如果n非常大,我认为这些算法会很慢.有没有办法让这两项操作更快/更有效？
谢谢
观看时Matt Godbolt 的演讲时时，我惊讶地发现，如果指示 Clang 针对 Haswell\xc2\xb9 架构进行编译，则会得出以下代码
\nint foo(int a) {\n int count = 0;\n while (a) {\n ++count;\n a &= a - 1;\n }\n return count;\n}\n用于计算设置位int（我不知道我自己需要多长时间才能计算出来），所以它只使用该指令：
foo(int): # @foo(int)\n popcntl %edi, %eax\n retq\n我想自己尝试一下，但我发现生成的代码是
\nfoo(int): # @foo(int)\n popcntl %edi, %eax\n cmovel %edi, %eax\n retq\n事实证明，生成的代码在 Clang 10.0.1 和 Clang 11.0.0 之间发生了变化。
\n为什么较新的 Clang 又发出了一条以前不需要的指令？代码是如此简单，以至于我无法理解多一条指令除了使代码变慢之外还能做什么（即使速度可能非常小，我不知道）。
\n\xc2\xb9 作为一个附带问题，事实上不指定-march=haswell会导致更长、更人性化的代码这一事实是否仅仅意味着该选项所针对的物理 CPU 具有用于执行设置位计数和其他操作的电路（好吧，不管 clang 默认是什么）不？
可能重复:
计算32位整数中设置位数的最佳算法？
给定32位整数N,设计算法以找到N的二进制位表示中的零的数量.
我能想到的最简单的算法是检查零的二进制表示,在C中是这样的:
int num_of_zero(int num)
{
if(0 == num) return 1; /*For the input 0 it should output 1 */
int Count = 0;
while(num>0){
if(0 == (num&1)) Count++;
num >>= 1;
}
return Count;
}
如果有一些算法在恒定时间计算,我就会徘徊.
对于输入0,它应该返回1 而不是32.
对于5,输出应为1.二进制表示为101.
对于7,输出应为0.
确切地说,我正在寻找一种更好的算法来计算32位整数的二进制解释中的(非前导)零的数量.希望问题现在很明显.
编辑:正如Alex Martelli指出的那样,我正在修改我的代码以使其更具可读性并且这次使用迭代.
我需要一个整数的快速哈希函数:
int hash(int n) { return ...; }
Java中是否存在某些东西？
我需要的最小属性是:
hash(n) & 1 当与一堆连续的n值一起使用时,它不会出现周期性.hash(n) & 1 大约同样可能是0或1.可能重复:
如何计算32位整数中的设置位数？
给出一个unsigned char类型值,计算它中的总位数.最快的方法是什么？我写了三个函数如下,最好的方法是什么,有人能想出一个更快的吗？(我只想要极快的一个)
const int tbl[] =
{
#define B2(n) n, n+1, n+1, n+2
#define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
#define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
B6(0), B6(1), B6(1), B6(2)
};
char naivecount (unsigned char val)
{
char cnt = 0;
while (val)
{
cnt += (val & 1);
val = val >> 1;
}
return cnt;
}
inline tableLookUp(int val)
{
assert(val >= 0 && val <= 255);
return tbl[val];
}
int asmCount(int val)
{
int res = …我一直在Go中使用汇编语言,我写了一个Hamming Weight函数作为练习.
我在这个SO答案上建立了一个原生的Go版本,而汇编版本是基于AMD的这个文档(第180页).在对两个函数进行基准测试后,我发现本机Go版本比汇编版本快1.5倍 - 2倍,尽管手写的汇编版本几乎与输出版本完全相同go tool 6g -S popcount.go.
输出来自 go test -bench=.
PASS
BenchmarkPopCount 100000000 19.4 ns/op
BenchmarkPopCount_g 200000000 8.97 ns/op
ok popcount 4.777s
popcount.go
package popcount
func popCount(i uint32) uint32 // Defined in popcount_amd64.s
func popCount_g(i uint32) uint32 {
i = i - ((i >> 1) & 0x55555555)
i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> …我正在尝试创建一个系统，该系统能够找到具有相似喜爱的电影/书籍/兴趣/等的用户，就像last.fm 上的邻居一样。具有最多共同兴趣的用户将具有最高的匹配度，并将显示在用户个人资料中（5 个最佳匹配左右）。
有没有相当快的方法来做到这一点？显而易见的解决方案是创建一个包含用户 id 和兴趣 id 的表，并将一个用户与所有其他用户进行比较，但这在一个表上需要很长时间......假设百万个用户每个都有 20 个兴趣。
我认为存在一些有效的解决方案，因为 last.fm 运行得很好。我更喜欢使用一些常见的 SQL 数据库，如 mySQL 或 pgSQL，但任何东西都可以。
感谢您的建议。
更新：
事实证明，最大的问题是在 SQL 数据库中查找最近邻居，因为没有一个开源数据库支持这种搜索。
所以我的解决方案是修改 ANN 以作为服务运行并从 PHP 查询它（例如使用套接字）——甚至拥有数百万用户，内存中有 7 个维度也没什么大不了的，而且运行速度快得令人难以置信。
针对较小数据集的另一个解决方案是这个简单的查询：
SELECT b.user_id, COUNT(1) AS mutual_interests
FROM `users_interests` a JOIN `users_interests` b ON (a.interest_id = b.interest_id)
WHERE a.user_id = 5 AND b.user_id != 5
GROUP BY b.user_id ORDER BY mutual_interests DESC, b.user_id ASC
20-50 毫秒，10 万用户平均每个用户有约 20 个兴趣（10 000 个可能的兴趣）
如何在UInt32不使用查找表的情况下计算设置位数(即计算1的数量)的最快方法是什么？有没有办法计算O(1)？
根据http://www.agner.org/optimize/instruction_tables.pdf,该POPCNT指令(返回32位或64位寄存器中的设置位数)在现代的每个时钟周期内具有1个指令的吞吐量英特尔和AMD处理器.这比需要多条指令的任何软件实现要快得多(如何计算32位整数中的设置位数？).
POPCNT如何在硬件中如此有效地实施？
考虑C ++标准库中的以下算法：std::shuffle该算法具有以下签名：
template <class RandomIt, class URBG>
void shuffle(RandomIt first, RandomIt last, URBG&& g);
它对给定范围内的元素进行重新排序，以使[first, last)这些元素的每个可能排列具有相同的出现概率。
我正在尝试实现相同的算法，但是它在位级别起作用，随机地对输入序列的单词的位进行改组。考虑到64位字的序列，我正在尝试实现：
template <class URBG>
void bit_shuffle(std::uint64_t* first, std::uint64_t* last, URBG&& g)
问题：如何尽可能有效地做到这一点（必要时使用编译器内部函数）？我并不一定要寻找一个完整的实现，而是要寻找更多的建议/研究方向，因为对于我来说，实际上是否有效地实现它尚不明确。