最重要的设置位的未设置位数?
假设64位整数0x000000000000FFFF
表示为
00000000 00000000 00000000 00000000 00000000 00000000 >11111111 11111111
如何找到最重要的设置位(标有>的那个)左侧的未设置位数?
// clear all bits except the lowest set bit x &= -x; // if x==0, add 0, otherwise add x - 1. // This sets all bits below the one set above to 1. x+= (-(x==0))&(x - 1); return 64 - count_bits_set(x);
其中count_bits_set
是您可以找到的最快的计数位版本。 有关各种位计数技术,请参阅https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel 。
在直接C(我的设置中很长的64位),取自类似的Java实现:(在更多关于汉明重量的阅读后更新)
更多解释:顶部只是将所有位置于最重要的1的右侧,然后否定它。 (即,最重要的1的’左’的0到现在都是1,其他一切都是0)。
然后我使用汉明重量实现来计算比特。
unsigned long long i = 0x0000000000000000LLU; i |= i >> 1; i |= i >> 2; i |= i >> 4; i |= i >> 8; i |= i >> 16; i |= i >> 32; // Highest bit in input and all lower bits are now set. Invert to set the bits to count. i=~i; i -= (i >> 1) & 0x5555555555555555LLU; // each 2 bits now contains a count i = (i & 0x3333333333333333LLU) + ((i >> 2) & 0x3333333333333333LLU); // each 4 bits now contains a count i = (i + (i >> 4)) & 0x0f0f0f0f0f0f0f0fLLU; // each 8 bits now contains a count i *= 0x0101010101010101LLU; // add each byte to all the bytes above it i >>= 56; // the number of bits printf("Leading 0's = %lldn", i);
我很想知道这是多么有效率。 虽然测试了几个值,它似乎工作。
基于: http : //www.hackersdelight.org/HDcode/nlz.c.txt
template int clz(T v) {int n=sizeof(T)*8;int c=n;while (n){n>>=1;if (v>>n) c-=n,v>>=n;}return cv;}
如果您想要一个允许您保持午餐的版本,请转到:
int clz(uint64_t v) { int n=64,c=64; while (n) { n>>=1; if (v>>n) c-=n,v>>=n; } return cv; }
正如您将看到的,您可以通过仔细分析汇编程序来节省周期,但这里的策略并不可怕。 while循环将运行Lg [64] = 6次; 每次它将问题转换为计算一半大小的整数的前导位数。 while循环中的if语句提出了一个问题:“我可以将这个整数表示为一半的位数”,或者类似地说,“如果我把它减半,我丢失了吗?”。 if()有效负载完成后,我们的数字将始终位于最低的n位。 在最后阶段,v为0或1,这样就可以正确完成计算。
如果您正在处理无符号整数,则可以执行以下操作:
#include int numunset(uint64_t number) { int nbits = sizeof(uint64_t)*8; if(number == 0) return nbits; int first_set = floor(log2(number)); return nbits - first_set - 1; }
我不知道它将如何在性能上与已经提供的循环和计数方法进行比较,因为log2()可能很昂贵。
编辑 :
这可能会导致高值整数出现一些问题,因为log2()
函数会转换为double
并且可能会出现一些数值问题。 您可以使用与long double
一起使用的log2l()
函数。 更好的解决方案是使用整数log2()
函数, 如此问题 。
我不确定我是否正确理解了这个问题。 我认为你有一个64位的值,并希望找到其中的前导零数。
一种方法是找到最高有效位并简单地从63减去其位置(假设最低位为位0)。 您可以通过测试是否在所有64位的循环内设置位来找出最重要的位。
另一种方法可能是在gcc中使用(非标准)__builtin_clz。
我同意二元搜索的想法。 但是这里有两点很重要:
- 您问题的有效答案范围为0到64( 含) 。 换句话说 – 这个问题可能有65个不同的答案。 我认为(几乎可以肯定)所有发布“二分搜索”解决方案的人都错过了这一点,因此在MSB位开启时,他们会得到零或数字的错误答案。
- 如果速度至关重要 – 您可能希望避免循环。 使用模板可以实现这一目标。
以下模板内容正确地找到任何无符号类型变量的MSB。
// helper template bool IsBitReached(T x) { const T cmp = T(1) << (bits ? (bits-1) : 0); return (x >= cmp); } template int FindMsbInternal(T x) { if (!bits) return 0; int ret; if (IsBitReached(x)) { ret = bits; x >>= bits; } else ret = 0; return ret + FindMsbInternal(x); } // Main routine template int FindMsb(T x) { const int bits = sizeof(T) * 8; if (IsBitReached(x)) return bits; return FindMsbInternal(x); }
在这里,您可以轻松更新,因为您需要其他尺寸……
int bits_left(unsigned long long value) { static unsigned long long mask = 0x8000000000000000; int c = 64; // doh if (value == 0) return c; // check byte by byte to see what has been set if (value & 0xFF00000000000000) c = 0; else if (value & 0x00FF000000000000) c = 8; else if (value & 0x0000FF0000000000) c = 16; else if (value & 0x000000FF00000000) c = 24; else if (value & 0x00000000FF000000) c = 32; else if (value & 0x0000000000FF0000) c = 40; else if (value & 0x000000000000FF00) c = 48; else if (value & 0x00000000000000FF) c = 56; // skip value <<= c; while(!(value & mask)) { value <<= 1; c++; } return c; }
与user470379相同的想法,但倒计时……
假设未设置所有64位。 当值大于0时,保持向右移动值并减少未设置位的数量:
/* untested */ int countunsetbits(uint64_t val) { int x = 64; while (val) { x--; val >>= 1; } return x; }
尝试
int countBits(int value) { int result = sizeof(value) * CHAR_BITS; // should be 64 while(value != 0) { --result; value = value >> 1; // Remove bottom bits until all 1 are gone. } return result; }
使用log base 2可以获得最重要的数字1。
log(2) = 1, meaning 0b10 -> 1 log(4) = 2, 5-7 => 2.xx, or 0b100 -> 2 log(8) = 3, 9-15 => 3.xx, 0b1000 -> 3 log(16) = 4 you get the idea
等等……中间的数字成为日志结果的一部分。 因此,将值类型转换为int可以为您提供最重要的数字。
一旦你得到这个数字,比如b,那么简单的64-n就是答案。
上述就是C#学习教程:最重要的设置位的未设置位数?分享的全部内容,如果对大家有所用处且需要了解更多关于C#学习教程,希望大家多多关注---计算机技术网(www.ctvol.com)!
function get_pos_msd(int n){ return int(log2(n)) } last_zero = 64 - get_pos_msd(n)
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/cdevelopment/998963.html