2

Let be a an unsigned int:

unsigned int a = 188; // 10111100

Is there a built-in function to get minor bit that is turn on? For example: in a case should return 2because first and second bits are zero's but the third is one.

// 10111100
//      ^
//      |-- Minor bit turn on

I'm using GCC and C99 standard.

4

7 回答 7

3

简单干净的解决方案：

#include <stdio.h>

int minor_bit(unsigned int x);

int main() {
    unsigned int a = 188;
    printf("%d\n", minor_bit(a));
    return 0;
}

int minor_bit(unsigned int x) {
    unsigned int i;
    if (x == 0)
        return -1;
    for (i = 0; !(x & 1U << i); i++);
    return i;
}
于 2013-09-23T19:45:53.963 回答
2

适用于高达 64 位。

static signed char f(uint64_t x)
{
    static const signed char p[] = { -1, 0, 1, 39, 2, 15, 40, 23, 3, 12,
        16, 59, 41, 19, 24, 54, 4, 0, 13, 10, 17, 62, 60, 28, 42, 30, 20,
        51, 25, 44, 55, 47, 5, 32, 0, 38, 14, 22, 11, 58, 18, 53, 63, 9,
        61, 27, 29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56,
        7, 48, 35, 6, 34, 33, };

    return p[(x & -x) % 67];
}

不清楚应该从0返回什么，所以我使用了-1。这显然是可以改变的。

于 2013-09-23T20:13:32.280 回答
2

这不是内置的，但可以工作......

尾随零计数（来自聚合 MAGIC 算法）

给定 Least Significant 1 Bit 和 Population Count (Ones Count) 算法，将它们组合起来构造一个尾随零计数是微不足道的（正如 Joe Bowbeer 所指出的）：

unsigned int
tzc(register int x)
{
    return(ones((x & -x) - 1));
}

哪里可以是 32 位：

unsigned int
ones32(register unsigned int x)
{
    /* 32-bit recursive reduction using SWAR...
   but first step is mapping 2-bit values
   into sum of 2 1-bit values in sneaky way
*/
    x -= ((x >> 1) & 0x55555555);
    x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
    x = (((x >> 4) + x) & 0x0f0f0f0f);
    x += (x >> 8);
    x += (x >> 16);
    return(x & 0x0000003f);
}
于 2013-09-23T19:38:00.273 回答
2

我相信这会成功。部分功劳归于解决方案。

int validate(unsigned value) {
  int count = 0;

  for (int i = 0; i < 8*sizeof(value); i++) { // 32 bits in unsigned int
    int bit = (value >> i) & 1;
    if (bit == 1) {
        break;
    } else {
        count++;
    }
  }

  return count;
}
于 2013-09-23T19:45:53.397 回答
1

一个适度但高度便携的解决方案。64 位
时最多 16 个循环。unsigned少于 N 的移位与 N-bit int。

int MinorBit(unsigned x) {
  if (x == 0) 
    return -1;  // special case, adjust as needed.
  int m = 0;
  // Search by char
  while ((x & ((1u << CHAR_BIT) - 1)) == 0) { 
    x >>= CHAR_BIT;
    m += CHAR_BIT;
  }
  // Search by bit
  while ((x & 1) == 0) { 
    x >>= 1;
    m++;
  }
  return m;
}
于 2013-09-23T20:11:05.553 回答
1

罗伯特，我认为这是更正确的（我认为，您必须将变量与计数器进行测试，而不是使用移位的计数器进行测试）

int minor(int value){
  int i=0;

  //Edge case (but could be fairly common)
  if (value == 0) {
    return -1; 
  }

  //Continuously left-shifts 1  and ANDs it with input value 
  //in order to find the first occurrence of the rightmost bit != 0
  while ((value & ( 1 << i )) == 0) {
     i++;
  }

  return i;

}
于 2013-09-23T19:59:39.080 回答
1

是的。由于您使用的是 GCC，因此您可以使用 __builtin_ctz 系列内置函数来跟踪零计数，

int __builtin_ctz (unsigned int x);

取自http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html。

例如，

2 == __builtin_ctz(188)

一个警告：对于输入 0，结果是未定义的。因此，它的使用可能需要受到保护，因此：

int safe_ctz(unsigned int x){
    return x ? __builtin_ctz(x) : 32;
}

这个内置的优点是对于某些目标，GCC 将其转换为一条指令，例如 x86 上的 BSF。

于 2013-09-25T01:23:23.577 回答