How to get minor bit turned on?

Question

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.

Answer 1

Yes. Since you're using GCC, you may use the __builtin_ctz family of built-in functions for trailing zero count,

int __builtin_ctz (unsigned int x);

as taken from http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html .

For instance,

2 == __builtin_ctz(188)

A word of warning: For the input 0, the result is undefined. Therefore its use may need to be guarded, thus:

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

The advantage of this builtin is that for some targets, GCC turns this to a single instruction, such as BSF on x86.

Answer 2

Simple and clean solution:

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

Answer 3

This is not built in, but works though...

Trailing Zero Count (from aggregate MAGIC algorithms)

Given the Least Significant 1 Bit and Population Count (Ones Count) algorithms, it is trivial to combine them to construct a trailing zero count (as pointed-out by Joe Bowbeer):

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

Where ones can be for 32 bit:

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

Answer 4

I believe this will do the trick. Partial credit goes to the solution.

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

Answer 5

Good for up to 64 bits.

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

It is not clear what should be returned from 0, so I used -1. That can be changed, obviously.

Answer 6

Robert, I think this is more correct (you have to AND the variable to test with the counter, not the shifted counter with itself, I think)

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;

}

Answer 7

A modest, yet highly portable solution.
Max 16 loops when unsigned is 64-bit. Less than N shifts with 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;
}