问题标签 [bitcount]

我正在使用 Java，我正在编写一个国际象棋引擎。

我试图在一个字节中找到前 1 位的索引和最后 1 位的索引。

我目前在 Java 中使用 Long.numberOfTrailingZeros() （或类似的东西），并希望模拟该功能，除了字节。

会不会是这样的：

如果是这样，我将如何相对有效地实现 bitCount。我不介意好的解释，请不要只给我代码。

获得以 2 为底的对数的最佳解决方案是什么，我知道是 2 的幂 ( 2^k)。（当然我只知道值2^k而不知道k它本身。）

我想到的一种方法是减去 1，然后进行位计数：

但是有没有更快的方法（没有缓存）？还有一些不涉及比特计数的东西会很高兴知道吗？

应用程序之一是：

为了在没有缓存的情况下比bitcount快，它应该比O(lg(k))存储k位的数量快。

我已经看到了许多关于计算insert type of输入中设置位数的问题，但它为什么有用呢？

对于那些寻找有关位计数的算法的人，请看这里：

1. 计算无符号长序列中的公共位
2. 计算无符号整数中位转换数的最快方法
3. 如何计算 32 位整数中设置的位数？

如何获得整数的位长，即在 Python 中表示正整数所需的位数？

http://www-graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

这与 Python 中的问题相同：来自 Bit Twiddling Hacks 的 C 代码的 Python 等价物？

我需要在 PHP 中使用此代码，独立于整数大小（上面的代码最多可以工作 128 位整数，这对我来说很好）。这是我尝试过的：

这不起作用的原因（在具有 64 位 PHP - Debian Squeeze 的 64 位机器上）是 PHP 似乎不支持 64 位无符号整数（如何在 PHP 上使用 64 位整数？）。恐怕我将不得不使用任意精度的数学库。还是有其他方法？

假设你有两个二进制值

您如何获得 MySQL 中不同位数的数量？我试过

这将返回 6，而在此示例中我需要一个返回 1 的解决方案。

MySQL 的 bit_count 函数在某些情况下非常有用：

http://dev.mysql.com/doc/refman/5.5/en/bit-functions.html#function_bit-count

现在我想在其他不支持它的数据库中使用该功能。最简单的方法是什么（不创建存储函数，因为我无权访问 DDL 级别的客户端数据库）。

一个非常冗长的选项是这个（对于TINYINT数据类型）：

对于 Sybase SQL Anywhere，该>>运算符似乎不可用，因此除法2, 4, 8, 16也可以。

还有其他不那么冗长的选项吗？

位计数可以通过多种方式完成，例如。具有设置位迭代器、未设置位迭代器、具有查找表或并行计数的预计算位。正如我通过搜索网络发现的那样，当未设置位较少时，未设置位迭代器速度很快，而设置位迭代器则相反。但是什么时候应该使用并行计数，尤其是 MIT HAKMEM（见下文）？它看起来相当快，虽然可能比查找表慢。就速度而言，它总是比设置/取消设置位更好吗？除了速度和内存之外，还有其他一些关于选择哪一个的问题吗？

我们可以假设 int 在 2 的补码中是 32 位唯一合法的运算符是：！~ & ^ | + << >>

在这一点上，我正在使用蛮力

...最后两条语句重复了 32 次。每次将 x 移动一位时，这会将 1 加到 a 上，对于所有 32 位，!= 0

使用测试编译器，它说我的方法在测试用例 0x7FFFFFFF（一个 0 后跟 31 个 1）上失败，并说这个数字需要 32 位来表示。我不明白为什么这不是 31 （我的方法计算出来的） 谁能解释为什么？我需要改变什么来解决这个问题？

我想计算在一个非常大的位向量（即 100,000 位）中设置的位。

我目前正在做的是使用指向 char 的指针（即 char *cPtr）来指向位数组的开头。我然后：

我突然想到，如果我改用一个短整型指针（即短整型 * sPtr），那么我只需要一半的查找次数，但使用 65534 个元素的查找表，这将有自己的成本内存使用情况。

我想知道每次检查的最佳位数是多少。此外，如果该数字不是某些预设类型的大小，我如何才能遍历我的位向量并将指针设置为超过位数组起始位置的任意位数。

我知道还有其他方法可以计算位数，但现在我想确定我可以在与其他方法进行比较之前优化此方法。