问题标签 [hammingweight]

我有以下任务：计算 1 和 N 之间有多少个数字恰好有 K 个零非前导位。（例如 7 ₁₀ =111 ₂将有 0 个，4 将有 2 个）

N 和 K 满足条件 0 ≤ K, N ≤ 1000000000

这个版本使用 POPCNT 并且在我的机器上足够快：

就速度而言（~0.8 秒）应该没问题，但它没有被接受，因为（我猜）测试服务器上使用的 CPU 太旧了，所以它表明发生了运行时错误。

我尝试使用带有 64K * 4 字节查找表的预计数技巧，但速度不够快：

(>1 秒)

我应该加速第二个程序（如果是，那么如何？）或以某种方式用其他一些（哪个？）指令替换 POPCNT（我猜应该可以使用 SSE2 和更早版本）？

我有一个方程组要求解，其中有一些汉明权重方程。汉明权重通常是数字的二进制表示中 1 的数量。我试图在 Z3 SMT Solver 中求解，但它输出一个错误，指出“b'there is no current model”。我试图找到一个具有给定汉明权重和一些方程的 32 位数字。

在下面的示例中，我试图找到一个汉明权重等于 3 的数字（0 到 2^5-1）。

这给出了错误“b'没有当前模型”。

谁能帮我解决这个问题？

编辑：我把汉明方程弄错了；这将是

谢谢

有人可以帮我在这个问题上停留几天。我想以 2 个十进制/十六进制的二进制值计算 1 的数字。但我得到的结果不正确。下面是一段代码：

C语言中popcnt函数的简单实现：

我正在使用内联汇编语言（x86-64）来实现popcnt，

但收到了WA（在线评委）

我在我的计算机上测试了 2 的所有幂（从 0x1 到 (0x1 << 63)），它返回 1，这表明我的 asm_popcnt 可以识别任何 64_bits 整数的所有位，因为所有其他整数只是 0x1、0x2、 0x4 等（例如，0x11a = 0x2“或”0x8“或”0x10“或”0x100）。因此，OJ 不应该返回“WA”。我的代码有什么问题吗？跳转指令？