我只需要用二进制运算(&,^,>>)来写一个汉字加权一个字节的表达式; 没有任何循环,只是一个公式.
我知道有很多算法可以计算汉明重量,但所有算法都使用算术运算或循环.
如果我们从http://en.wikipedia.org/wiki/Hamming_weight获取算法,那么第一个和D = B + C可以写成D = B ^ C ^(B&C << 1),但是后面的两个和更复杂.
有人有提示吗？
更新:谢谢你的帮助.实际上,我需要以下内容:
int popcount_1(unsigned char in){
unsigned char m1 = 0x55;
unsigned char m2 = 0x33;
unsigned char m4 = 0x0f;
unsigned char B,C = 0;
unsigned char x = in;
x = (x & (x << 1) & (m1 << 1)) | (m1 & (x ^ (x >> 1)));
B = x & m2;
C = (x >> 2) & m2;
x …我想检查数字是否将所有偶数或奇数位设置为1并且仅将它们设置为1.例如:
数字42是正确的,因为在二进制代码中101010它具有全部且仅偶数位设置为1.数字21也是正确的10101.
编号69为如.1000101是不正确的,因为只有三个奇数位组1.
我尝试过使用不同的操作,但^, &, >>, <<我仍然不知道如何使用这些操作符来完成此操作.是的,我需要使用逻辑运算符来执行此操作C.
假设我需要为0 ... 255值创建一个包含预先计算的位计数值(数字中的1位数)的LUT:
int CB_LUT[256] = {0, 1, 1, 2, ... 7, 8};
如果我不想使用硬编码值,我可以使用漂亮的模板解决方案如何计算32位整数中的设置位数？
template <int BITS>
int CountBits(int val)
{
return (val & 0x1) + CountBits<BITS-1>(val >> 1);
}
template<>
int CountBits<1>(int val)
{
return val & 0x1;
}
int CB_LUT[256] = {CountBits<8>(0), CountBits<8>(1) ... CountBits<8>(255)};
该数组在编译时完全计算.有没有办法避免长列表,并使用某种模板甚至宏生成这样的数组(抱歉!),如:
Generate(CB_LUT, 0, 255); // array declaration
...
cout << CB_LUT[255]; // should print 8
笔记.这个问题不是关于计算一个数字中的1位,而是仅用作示例.我想在代码中完全生成这样的数组,而不使用外部代码生成器.必须在编译时生成数组.
编辑.为了克服编译器限制,我找到了以下解决方案,基于Bartek Banachewicz代码:
#define MACRO(z,n,text) CountBits<8>(n)
int CB_LUT[] = {
BOOST_PP_ENUM(128, MACRO, _)
};
#undef …我目前正在跟踪视频的用户播放时间,我正在尝试确定用户观看的视频的百分比.我已经将问题推广到给定一系列可能重叠的数字范围,如何将它们组合成一系列非重叠的数字范围(即转换为"0-10,5-15,30-45,20-25")进入"0-15,20-25,30-45".
我有一个相对冗长的解决方案,前提是如果对数字范围进行排序,那么组合两个相邻的数字范围相对微不足道(如果它们重叠或者它们保持分离,则将它们组合起来).因此,我们首先对数字范围进行排序,然后遍历范围并组合它们.
由于排序是最坏的情况O(nlgn),这意味着我的解决方案应该是O(nlgn),我想知道是否有人知道O(n)问题的解决方案？
var testcase = [
[0, 30], [40, 50], [5, 15], [70, 95], [45, 75], [0, 10],
[110, 115], [115, 120], [140, 175], [125, 160]
];
//sorts the array in ascending order (based on first element)
//if the first elements are the same, order based on second element (prioritising elements that are bigger)
testcase.sort(function(a, b) {
if (a[0] !== b[0]) return a[0] - b[0];
return b[1] - a[1]
})
function evaluate(a, b) {
var result = []; …有没有办法使用内在函数来优化以下代码？它获取 16 位整数中的所有奇数索引位，并将它们尽可能向右移动。
我在想也许可以使用 Fortran 中 IHFTC 的 C++ 等效项（是否有与此等效的 C++ 版本？）。但我觉得还有更有效的方法。
int x = some16bitInt;
x = x&0x5555;
int y = 0;
for (int i = 0; i < 8; i++)
y = y | ((x >> i) & (0x01 << i));
'''
我有一个整数数组：
[int1, int2, ..., intn]
我想计算这些整数的二进制表示中有多少非零位。
例如：
bin(123) -> 0b1111011, there are 6 non-zero bits
当然，我可以遍历整数、用途bin()和count('1')函数的列表，但我正在寻找矢量化的方法来做到这一点。
我正在寻找一种在两个位置之间的bitstring中查找pop计数的解决方案,例如:
popcnt( 10(0101), 0, 3) = 1
popcnt( 100101(), 0, 0) = 0
popcnt( 10010(1), 0, 1) = 0
**我假设开放范围并假设从右到左的顺序
使用标准位运算符以及可能的popcnt或等效运算符.
如果它有所不同,我希望找到两个字符串的差异之间的popcnt.让我说我有字符串b,我在两个位置交换位,例如0101110 -> 1101100 => 3- 我需要改变位之间的popcnt - 在两者之间的位的情况下,所以popcnt是30101110 -> 110110010110
你有没有看到一些巧妙的方法来做bithacks？
当我遇到这个问题时,我正在努力创建一个稀疏的八叉树实现,就像nVidia ("Efficient Sparse Voxel Octrees")的人们为他们的体素做的那样:
我有一个字节类型的字节(只有8位)告诉我八叶树的叶子在哪里(1表示叶子,0表示没有叶子,8个节点附着 - > 8位).我现在要做的是返回叶子位置的数组.我当前的实现是使用while循环来确定是否设置了LSB.之后输入移1.所以这就是我这样做的方式:
int leafposition = _leafmask & _validmask;
int[] result = new int[8];
int arrayPosition = 0;
int iteration = 0;
while ( leafposition > 0 )
{
iteration++; //nodes are not zero-indexed ... ?
if ( (leafposition & 1) == 1 ) // LSB set?
{
result.SetValue( iteration, arrayPosition );
arrayPosition++;
};
leafposition = leafposition >> 1;
}
return result;
这看起来并不优雅,有两件令人不安的事情:
我希望结果与[2,4,6]42 相似(0010 1010).
任何人都可以提供更优雅的解决方案仍然可读吗？ …
我有一个32位随机值(比方说631).
0...0000001001110111
每个位都是一个标志.如果可能的话,我想从这些位返回一个随机标志,进行O(1)操作.如何从给定值中选择位位置0,1,2,4,5,6或9(或它的对应值1,2,4,16,32,64,512)631？优选地,对于某些位具有至少可能的偏置.
我提出的事情:
上面不是O(1),如果我们碰巧只"击中"0位,可能需要多次迭代.
同样,不幸的是,上面不是O(1).
我很确定这必须是可能的,有些bithisfting/masking /魔法......
编辑:
正如CodeCaster建议的那样 ; 这将给我所有设置位值:
int myvalue = 631;
var matchingmasks = Enumerable.Range(0, 32)
.Select(i => 1 << i)
.Where(i => (myvalue & i) == i)
.ToArray();
从结果数组中我可以选择一个随机元素,我将从给定值中找到我的"随机"位(标志).但是,这仍然需要一个(隐藏的,因为Linq)for循环,"强制"每个可能的位,结果数组的内存分配等.
是否有一种简单的方法可以将单个数字的所有位进行XOR运算，即C中的一元XOR？
具有以下作用的东西：
result = ^(0x45); // ( 0 ^ 1 ^ 0 ^ 0 ^ 0 ^ 1 ^ 0 ^ 1 = 1)
result = ^(0x33); // ( 0 ^ 0 ^ 1 ^ 1 ^ 0 ^ 0 ^ 1 ^ 1 = 0)