可能重复:
计算32位整数中设置位数的最佳算法？
我想编写一个程序来比较两个数字得到1位数.如果我比较任意两个数字之间的位,找到二进制数在1和0中的不同位置.换句话说,异或(XOR)关系.
比如22(有10110二进制)并将它与15(有01111二进制)进行比较
第一个10110
第二个01111
结果11001
答案是25,但我想要的是3,其中有3个1和0是不同的.
以下是std::bitset::countMSVC 2010 的实现:
size_t count() const
{ // count number of set bits
static char _Bitsperhex[] = "\0\1\1\2\1\2\2\3\1\2\2\3\2\3\3\4";
size_t _Val = 0;
for (int _Wpos = _Words; 0 <= _Wpos; --_Wpos)
for (_Ty _Wordval = _Array[_Wpos]; _Wordval != 0; _Wordval >>= 4)
_Val += _Bitsperhex[_Wordval & 0xF];
return (_Val);
}
有人可以向我解释这是如何工作的吗？诀窍是_Bitsperhex什么？
我只是想在php中找到一些最快的设置位计数功能.
例如,0010101 => 3,00011110 => 4
我看到有很好的算法可以在c ++中实现. 如何计算32位整数中的设置位数？
是否有任何php内置函数或最快的用户自定义函数？
假设我们有K个二进制数(每个都是相同的长度).我们需要找到所需的最少位数(不需要是连续的)来唯一地识别这些K二进制数.例如100,110可以区分1位(在第二位置).111,110,101需要2比特来区分.
我搜索了一种算法，该算法通过 O(1) 的时间复杂度以及我在谷歌中找到的内容来计算 Byte 中的个数：
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
int BitsSetTable256[256];
// Function to initialise the lookup table
void initialize()
{
// To initially generate the
// table algorithmically
BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++)
{
BitsSetTable256[i] = (i & 1) +
BitsSetTable256[i / 2];
}
}
// Function to return the count
// of set bits in n
int countSetBits(int n)
{
return (BitsSetTable256[n & 0xff] …我有一个32位数字,想知道有多少位是1.
我在考虑这个伪代码:
mov eax, [number]
while(eax != 0)
{
div eax, 2
if(edx == 1)
{
ecx++;
}
shr eax, 1
}
有更有效的方法吗？
我在x86处理器上使用NASM.
(我刚开始使用汇编程序,所以请不要告诉我使用extern库中的代码,因为我甚至不知道如何包含它们;))
(我刚刚发现如何计算32位整数中的设置位数？这也包含我的解决方案.还有其他解决方案,但不幸的是我似乎无法弄清楚,我将如何在汇编程序中编写它们)
给定N作为位数,K作为1的数量,如何生成包含K个和Nk零的所有二进制表示？
换句话说,我有:
N=4 //number of bits
K=2 //number of ones
包含N位,K个和NK零的所有可能二进制值是:
1100
1010
1001
0110
0101
0011
到目前为止我什么都没有.我不是要求代码.我只想问最好的方法吗？一个算法？伪代码？也许是讨论？
编辑:我要求代码/伪代码来解决问题...而不是数学公式......
我需要确定某个类型的变量(可能是32位无符号或64位无符号)中设置的位数是否为奇数.我读了:
这当然非常有用,但我想做得更好,因为我只需要二进制答案,而不是整个计数.我想更换一个字节或两个字节的LUT应该非常快,但也许非LUT代码可以以某种方式改进.
我知道之前有人问过,但我正在看这里列出的特定解决方案:
int BitCount(unsigned int u)
{
unsigned int uCount;
uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
return ((uCount + (uCount >> 3)) & 030707070707) % 63;
}
它是如何工作的？
这里有什么警告吗？
理论上可以在恒定的时间内找到答案吗？我的意思是,我们实际上不必迭代这些位来计算？
我正在尝试计算大量uint64的位奇偶校验.比特奇偶校验是指接受uint64的函数,如果设置的比特数是偶数则输出0,否则为1.
目前我正在使用以下功能(@Troyseph,在这里找到):
uint parity64(uint64 n){
n ^= n >> 1;
n ^= n >> 2;
n = (n & 0x1111111111111111) * 0x1111111111111111;
return (n >> 60) & 1;
}
相同的SO页面具有以下汇编例程(由@papadp提供):
.code
; bool CheckParity(size_t Result)
CheckParity PROC
mov rax, 0
add rcx, 0
jnp jmp_over
mov rax, 1
jmp_over:
ret
CheckParity ENDP
END
它利用了机器的奇偶校验标志.但我不能让它与我的C程序一起工作(我知道旁边没有汇编).
问题.如何在C源文件中包含上面(或类似)代码作为内联汇编,以便该parity64()函数运行该代码？
(我在Intel Xeon Haswell上使用GCC和64位Ubuntu 14)
如果它有任何帮助,则parity64()在以下例程中调用该函数:
uint bindot(uint64* a, uint64* b, uint64 entries){
uint parity …