如何在没有实际转换和计数的情况下获得数字的二进制表示中的"1"的数量？
例如
def number_of_ones(n):
# do something
# I want to MAKE this FASTER (computationally less complex).
c = 0
while n:
c += n%2
n /= 2
return c
>>> number_of_ones(5)
2
>>> number_of_ones(4)
1
我刚刚完成了计算机科学1的作业问题(是的,这是家庭作业,但是听我说!).现在,作业完成并且有效,所以我不需要帮助.我的问题涉及我正在使用的算法的效率(我们尚未对算法效率进行评分,我只是非常好奇).
我对目前提出的函数使用线性搜索算法的修改版本(即我想出了,全部由我自己!),以检查如何在给定的彩票多的数字相匹配的中奖号码,假设两机票上的数字和绘制的数字按升序排列.我想知道,有没有办法让这个算法更有效率？
/*
* Function: ticketCheck
*
* @param struct ticket
* @param array winningNums[6]
*
* Takes in a ticket, counts how many numbers
* in the ticket match, and returns the number
* of matches.
*
* Uses a modified linear search algorithm,
* in which the index of the successor to the
* last matched number is used as the index of
* the first number tested for the next ticket value.
*
* @return int numMatches …如果具有偶数1位,则值具有偶数奇偶校验.如果具有奇数1位,则该值具有奇校验.例如,0110具有偶校验,并1110具有奇校验.
1如果x有平价,我必须返回.
int has_even_parity(unsigned int x) {
return
}
这是网站上搜索功能的一部分.所以我试图找到一种尽可能快地达到最终结果的方法.
有一个数字顺序重要的二进制数.
输入数字= 01001
拥有一个长度相同的其他二进制数的数据库.
01000,10110,00000,11141
我不知道怎么写我正在做什么,所以我将在下面更直观地做.
// Zeros mean nothing & the location of a 1 matters, not the total number of 1's.
input num > 0 1 0 0 1 = 2 possible matches
number[1] > 0 1 0 0 0 = 1 match = 50% match
number[2] > 1 0 1 1 0 = 0 match = 0% match
number[3] > 0 0 0 0 0 = 0 match = 0% match
number[4] > 1 1 1 …有谁能告诉我什么是一个有效的算法来计算C编程中32位无符号整数中前导零的数量？
在采访新的候选者时,我们通常会要求他们写一段C代码来计算给定字节变量中值为1的位数(例如,字节3有两个1位).我知道所有常见的答案,例如右移八次,或索引256个预先计算结果的常数表.
但是,如果没有使用预先计算的表,是否有更聪明的方法？什么是字节操作(AND,OR,XOR,+, - ,二进制否定,左移和右移)的最短组合,它计算1位的数量？
我想知道,如何有效地计算hashCode类似BitSet的实现Set<Integer>.
该BitSet#hashCode显然是快速地计算,而愚蠢的(*)和不兼容的Set#hashCode().
快速兼容的实现可能会像
int hashCode() {
int result = 0;
for (int i=0; i<bits.length; ++i) {
long word = bits[i];
result += 64 * i * Long.bitCount(word) + weightedBitCount(word);
}
return result;
}
如果有一个有效的实施
int weightedBitCount(long word) { // naive implementation
int result = 0;
for (int i=0; i<64; ++i) {
if ((word & (1L << i)) != 0) {
result += i;
}
}
return result;
}
如果未设置大多数位,可以通过测试word==0 …
给定一个整数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非常大,我认为这些算法会很慢.有没有办法让这两项操作更快/更有效？
谢谢
可能重复:
计算32位整数中设置位数的最佳算法？
嗨,
我在接受采访时遇到了这个问题.我想以优化的方式找到给定数字中的设置位数.
示例:
如果给定的数字是7,那么输出应该是3(因为7的二进制是111,我们有三个1)
如果给定的数字8然后输出应该是1(因为8的二进制是1000,我们有一个1)
我们需要以优化的方式找到一些.有什么建议？
我有一大块内存,比如256 KiB或更长.我想计算整个块中的1位数,或者换句话说:为所有字节添加"种群计数"值.
我知道AVX-512有一个VPOPCNTDQ指令,它计算512位向量中每个连续64位的1位数,而IIANM应该可以在每个周期发出其中一个(如果一个适当的SIMD向量寄存器是可用) - 但我没有任何编写SIMD代码的经验(我更像是一个GPU人).此外,我不是100%确定AVX-512目标的编译器支持.
在大多数CPU上,仍然没有(完全)支持AVX-512; 但AVX-2广泛可用.我无法找到类似于VPOPCNTDQ的低于512位的向量化指令,所以即使理论上我也不确定如何使用支持AVX-2的CPU快速计算位数; 也许这样的事情存在,我只是错过了它？
无论如何,对于两个指令集中的每一个,我都很欣赏一个简短的C/C++函数 - 使用一些内部包装库或内联汇编.签名是
uint64_t count_bits(void* ptr, size_t size);
笔记: