7

我有一个byte我正在使用的位标志。我知道在任何给定时间都设置了一个且只有一个位。byte

前任：unsigned char b = 0x20; //(00100000) 6th most bit set

我目前使用以下循环来确定设置了哪个位：

int getSetBitLocation(unsigned char b) {
  int i=0;
  while( !((b >> i++) & 0x01) ) { ; }
  return i;
}

如何最有效地确定设置位的位置？我可以在没有迭代的情况下做到这一点吗？

4

8 回答 8

7

我可以在没有迭代的情况下做到这一点吗？

这确实是可能的。

如何最有效地确定设置位的位置？

你可以试试这个算法。它将字符分成两半以搜索最高位，每次都转移到低半部分：

int getTopSetBit(unsigned char b) {
  int res = 0;
  if(b>15){
    b = b >> 4;
    res = res + 4;
  }
  if(b>3){
    b = b >> 2;
    res = res + 2;
  }

  //thanks @JasonD
  return res + (b>>1);
}

它使用两个比较（三个用于uint16s，四个用于uint32s...）。它可能比你的循环更快。绝对不会更短。

基于 Anton Kovalenko 的想法（散列查找）和 6502 的评论（除法很慢），我还建议这种实现（使用de-Bruijn序列的 8 位 => 3 位散列）

int[] lookup = {7, 0, 5, 1, 6, 4, 3, 2};

int getBitPosition(unsigned char b) {
  // return lookup[(b | (b>>1) | (b>>2) | (b>>4)) & 0x7];
  return lookup[((b * 0x1D) >> 4) & 0x7];
}

或（更大的 LUT，但仅使用三个术语而不是四个）

int[] lookup = {0xFF, 0, 1, 4, 2, 0xFF, 5, 0xFF, 7, 3, 0xFF, 0xFF, 6, 0xFF, 0xFF, 0xFF};

int getBitPosition(unsigned char b) {
  return lookup[(b | (b>>3) | (b>>4)) & 0xF];
}
于 2013-01-20T21:54:25.903 回答
5

查找表很简单，如果值集很稀疏，您可以减小它的大小。让我们尝试使用 11 个元素而不是 128 个元素：

unsigned char expt2mod11_bits[11]={0xFF,0,1,0xFF,2,4,0xFF,7,3,6,5};
unsigned char pos = expt2mod11_bits[b%11];
assert(pos < 8);
assert(1<<pos == b);

当然，它不一定更有效，尤其是对于 8 位，但同样的技巧可以用于更大的尺寸，其中完整的查找表会非常大。让我们来看看：

unsigned int w; 
....
unsigned char expt2mod19_bits[19]={0xFF,0,1,13,2,0xFF,14,6,3,8,0xFF,12,15,5,7,11,4,10,9};
unsigned char pos = expt2mod19_bits[w%19];
assert(pos < 16);
assert(1<<pos == w);
于 2013-01-20T22:01:42.650 回答
3

对于使用 64 位来表示位置的国际象棋程序来说，这是一个非常常见的问题（即，一个 64 位数字存储所有白棋在哪里，另一个存储所有黑棋在哪里，依此类推）。

使用这种表示，有时需要找到第一个或最后一个设置位的索引 0...63，并且有几种可能的方法：

  1. 像你一样做一个循环
  2. 使用二分搜索（即如果x & 0x00000000ffffffffULL为零，则无需检查低 32 位）
  3. 如果处理器上可用，则使用特殊指令（例如bsf，bsr在 x86 上）
  4. 使用查找表（当然不是针对整个 64 位值，而是针对 8 位或 16 位）

然而，更快的方法实际上取决于您的硬件和实际用例。对于仅 8 位和现代处理器，我认为可能具有 256 个条目的查找表是最佳选择......

但是你真的确定这是你算法的瓶颈吗？

于 2013-01-20T22:05:07.630 回答
2

基于 Find the log base 2 of an N-bit integer in O(lg(N)) operations 中的log2 计算：

int getSetBitLocation(unsigned char c) {
  // c is in {1, 2, 4, 8, 16, 32, 64, 128}, returned values are {0, 1, ..., 7}
  return (((c & 0xAA) != 0) |
          (((c & 0xCC) != 0) << 1) |
          (((c & 0xF0) != 0) << 2));
}
于 2013-01-20T22:47:50.370 回答
2 
unsigned getSetBitLocation(unsigned char b) {
  unsigned pos=0;
  pos = (b & 0xf0) ? 4 : 0; b |= b >>4;
  pos += (b & 0xc) ? 2 : 0; b |= b >>2;
  pos += (b & 0x2) ? 1 : 0; 
  return pos; 
}

很难做到无跳跃。也许与 Bruin 序列有关？

于 2013-01-20T21:55:21.087 回答
1

最简单的事情是创建一个查找表。最简单的将是稀疏的（有 256 个元素），但从技术上讲它会避免迭代。

这里的评论在技术上避免了迭代，但我们在开玩笑，它仍然在做同样数量的检查：How to write log base(2) in c/c++

封闭形式将是log2()，一个 la，log2() + 1但我不确定它的效率如何 - 可能 CPU 有一条指令用于以 2 为底的对数？

于 2013-01-20T21:50:10.157 回答
0

如果你定义

const char bytes[]={1,2,4,8,16,32,64,128}

并使用

struct byte{
char data;
int pos;
}
void assign(struct byte b,int i){

b.data=bytes[i];
b.pos=i
}

您不需要确定设置位的位置

于 2013-01-20T21:55:45.167 回答
0

当 CHAR_BIT == 8 时，查找表又快又容易，但在某些系统上，CHAR_BIT == 16 或 32 并且查找表变得异常庞大。如果您正在考虑使用查找表，我建议将其包装起来；改为“查找表函数”，以便在需要优化时交换逻辑。

使用分治法，通过对排序数组执行二进制搜索，涉及基于 log2 的比较CHAR_BIT。该代码更复杂，涉及初始化数组unsigned char以用作开始的查找表。一旦你初始化了这样的数组，你就可以使用bsearch它来搜索它，例如：

#include <stdio.h>
#include <stdlib.h>
void uchar_bit_init(unsigned char *table) {
    for (size_t x = 0; x < CHAR_BIT; x++) {
        table[x] = 1U << x;
    }
}
int uchar_compare(void const *x, void const *y) {
    char const *X = x, *Y = y;
    return (*X > *Y) - (*X < *Y);
}
size_t uchar_bit_lookup(unsigned char *table, unsigned char value) {
    unsigned char *position = bsearch(lookup, c, sizeof lookup, 1, char_compare);
    return position ? position - table + 1 : 0;
}
int main(void) {
    unsigned char lookup[CHAR_BIT];
    uchar_bit_init(lookup);
    for (;;) {
        int c = getchar();
        if (c == EOF) { break; }
        printf("Bit for %c found at %zu\n", c, uchar_bit_lookup(lookup, c));
    }
}

PS这听起来像是微优化。完成您的解决方案（将所需的操作抽象到这些函数中），然后担心基于您的分析的优化。如果您要专注于微优化，请确保您的分析针对您的解决方案将运行的系统，因为微优化的效率差异很大，因为硬件甚至略有不同......通常购买一个更好的主意更快的电脑；）

于 2013-01-20T21:59:03.263 回答