确定设置了字节中的哪个位 [英] Determine which single bit in the byte is set

问题描述

我有一个 byte 用于 bitflags.我知道 byte 中的只有一个 位在任何给定时间被设置.

I have a byte I'm using for bitflags. I know that one and only one bit in the byte is set at any give time.

例如:unsigned char b = 0x20;//(00100000) 第六位设置

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

I currently use the following loop to determine which bit is set:

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

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

How do I most efficiently determine the position of the set bit? Can I do this without iteration?

推荐答案

我可以在不迭代的情况下做到这一点吗?

Can I do this without iteration?

确实有可能.

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

How do I most efficiently determine the position of the set bit?

你可以试试这个算法.它将字符分成两半以搜索高位，每次都移到低位:

You can try this algorithm. It splits the char in half to search for the top bit, shifting to the low half each time:

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...).它可能比你的循环更快.绝对不会更短.

It uses two comparisons (three for uint16s, four for uint32s...). and it might be faster than your loop. It is definitely not shorter.

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

Based on the idea by Anton Kovalenko (hashed lookup) and the comment by 6502 (division is slow), I also suggest this implementation (8-bit => 3-bit hash using a de-Bruijn sequence)

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，但只使用三个而不是四个)

or (larger LUT, but uses just three terms instead of four)

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];
}

这篇关于确定设置了字节中的哪个位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！