bit position

[Serve Laurijssen]

What would be an optimal way to get the position of the lowest bit where you
know only 1 bit will be on 1?
Like in the position of bit 0x8 is 4, 0x4 it's 3 etc.

Best thing I could come up with is

#define BITPOS(x) \

((x) & 0x1 ? 1 : \

(x) & 0x2 ? 2 : \

(x) & 0x4 ? 3 : \

(x) & 0x8 ? 4 : 0)



int main(void) {

unsigned short x = 0x0008;

while (x) {

printf("%d\n", BITPOS(x));

x >>= 4;

}


return 0;

}

 

[Richard Heathfield]

Serve Laurijssen said:

What would be an optimal way to get the position of the lowest bit where
you know only 1 bit will be on 1?

If you have an n-bit unsigned integer type, start off by comparing the value
with (1 << (n / 2)), and home in on the bit using binary search, for O(log
n) instead of O(n).

 

[Giorgio Silvestri]

What would be an optimal way to get the position of the lowest bit where you
know only 1 bit will be on 1?
Like in the position of bit 0x8 is 4, 0x4 it's 3 etc.

Best thing I could come up with is

#define BITPOS(x) \

((x) & 0x1 ? 1 : \

(x) & 0x2 ? 2 : \

(x) & 0x4 ? 3 : \

(x) & 0x8 ? 4 : 0)



int main(void) {

unsigned short x = 0x0008;

while (x) {

printf("%d\n", BITPOS(x));

x >>= 4;

}


return 0;

}

Another possibility is a 'look-up table':

/*
* for nibbles: position of 'lowest 1', (0 if missing)
*/
int bitpos[] = {
0, /* 0 0 0 0 */
1, /* 0 0 0 1 */
2, /* 0 0 1 0 */
1, /* 0 0 1 1 */
3, /* 0 1 0 0 */
1, /* 0 1 0 1 */
2, /* 0 1 1 0 */
1, /* 0 1 1 1 */
4, /* 1 0 0 0 */
1, /* 1 0 0 1 */
2, /* 1 0 1 0 */
1, /* 1 0 1 1 */
3, /* 1 1 0 0 */
1, /* 1 1 0 1 */
2, /* 1 1 1 0 */
1, /* 1 1 1 1 */
};

/*
* usage
*/
bitp = bitpos[0xF & x];

 

[Serve Laurijssen]

What would be an optimal way to get the position of the lowest bit where
you know only 1 bit will be on 1?
Like in the position of bit 0x8 is 4, 0x4 it's 3 etc.

so there isnt some bid fiddle solution to this?

 

[Eric Sosman]

Serve Laurijssen wrote On 10/25/06 17:27,:

so there isnt some bid fiddle solution to this?

One trick that's sometimes used is to convert the value
to floating-point and then look at the exponent:

#include <math.h>
int bitpos(unsigned long one_bit_is_set) {
int exponent;
(void) frexp(one_bit_is_set, &exponent);
return exponent - 1;
}

.... but whether this counts as "optimal" is open to question.
Usually, this trick is used along with a bunch of non-portable
knowledge about the machine's floating-point hardware instead
of relying on the portable frexp() function. Even with such
knowledge, some machines may not perform well if there's too
much cross-talk between the integer and F-P componentry.

 

[Eric Sosman]

Eric Sosman wrote On 10/25/06 17:46,:

Serve Laurijssen wrote On 10/25/06 17:27,:



One trick that's sometimes used is to convert the value
to floating-point and then look at the exponent:

#include <math.h>
int bitpos(unsigned long one_bit_is_set) {
int exponent;
(void) frexp(one_bit_is_set, &exponent);
return exponent - 1;

Just noticed that this returns the more usual bit
numbering: 1->0, 8->3, 32->5 and so on. For the off-
by-one numbering you asked for, just return `exponent'
and omit the `- 1'.

 

[Nishu]

What would be an optimal way to get the position of the lowest bit where you
know only 1 bit will be on 1?

Optimal in terms of size or execution speed? and then again it is
dependent on the processor you are working on. Usual method is, shift
the number by one and compare with zero, other alternatives includes
look up tables (at increased cost of size), use of special instructions
to count the leading zeros and so on...

-Nishu

 

[Ico]

What would be an optimal way to get the position of the lowest bit where you
know only 1 bit will be on 1?
Like in the position of bit 0x8 is 4, 0x4 it's 3 etc.

Best thing I could come up with is

#define BITPOS(x) \

((x) & 0x1 ? 1 : \
(x) & 0x2 ? 2 : \
(x) & 0x4 ? 3 : \
(x) & 0x8 ? 4 : 0)

There are a number of recipes for this problem in the book 'Hackers
Delight'. A lot depends on the type of CPU you are using, and if you
want fast execution or small code size.

This is a basic binary search technique : [code fragments from Hackers
Delight]

if (x == 0) return(32);
n = 0;
if (x <= 0x0000FFFF) {n = n +16; x = x <<16;}
if (x <= 0x00FFFFFF) {n = n + 8; x = x << 8;}
if (x <= 0x0FFFFFFF) {n = n + 4; x = x << 4;}
if (x <= 0x3FFFFFFF) {n = n + 2; x = x << 2;}
if (x <= 0x7FFFFFFF) {n = n + 1;}
return n;

Or the other way around, counting down:

int nlz(unsigned x)
{
unsigned y;
int n;

n = 32;
y = x >>16; if (y != 0) {n = n -16; x = y;}
y = x >> 8; if (y != 0) {n = n - 8; x = y;}
y = x >> 4; if (y != 0) {n = n - 4; x = y;}
y = x >> 2; if (y != 0) {n = n - 2; x = y;}
y = x >> 1; if (y != 0) return n - 2;
return n - x;
}


If you prefer speed over code size, a table lookup would probably be the
fastest solution:

static char table[256] = {0,1,2,2,3,3,3,3,4,4,...,8);
return n - table[x];

 

[Simon Biber]

so there isnt some bid fiddle solution to this?

Well you can take Richard's suggestion and code it as a binary search:

int lowest_bit_pos(unsigned long long v)
{
int top = CHAR_BIT * sizeof(unsigned long long);
int bot = 0;
int a = (top + bot) / 2;
unsigned long long tv = 1ULL << a;
while(v != tv)
{
if(top == bot || top == bot + 1) return -1; /* 0 or >1 bits set */
if(v < tv) top = a; else bot = a;
a = (top + bot) / 2;
tv = 1ULL << a;
}
return a;
}

Or you could just use floating-point maths:

int lowest_bit_pos(unsigned long long v)
{
return round(log(v) / log(2));
}

 

[Hallvard B Furuseth]

What would be an optimal way to get the position of the lowest bit
where you know only 1 bit will be on 1?

Possibly the POSIX ffs() function in <string.h>. Or if the value is
an 8-bit byte, you could use 7 - 86/(val + 11). Don't know how they
compare with some of the other methods in this thread, though.

 

[Keith Thompson]

Possibly the POSIX ffs() function in <string.h>.

[...]

<OT>
ffs() is not declared in <string.h>. Consult your documentation for
more information, or try comp.unix.programmer.
</OT>

 

[Hallvard B Furuseth]

Possibly the POSIX ffs() function in <string.h>.

[...]

<OT>
ffs() is not declared in <string.h>.

Consult your documentation for more information,

I did, and misread. I know strings.h isn't used anymore, right?

 

[Dave Thompson]

What would be an optimal way to get the position of the lowest bit where you
know only 1 bit will be on 1?
Like in the position of bit 0x8 is 4, 0x4 it's 3 etc.

A mathematically clever way is to choose an integer N not much larger
than the width of your input values such that the multiplicative group
Z_n^* is generated by 2, and precompute (at build time or process
startup) the discrete log2 table; then given a value P with only one
bit set hence a power of two, P % N is a unique value and looking it
up in your table gives the answer. For example for 32 bits use 37.

However, general % is implemented using a divide operation and
possibly a multiply, or at best two chained multiplies, and on most if
not all modern computers that is slower than the bitfiddling or even
lookuptable methods. Plus most other e.g. maintenance programmers will
quickly understand those, but will need comments for the Z_n method.

If you have an unsigned int or wider X with (possibly) more than one
bit set, you can easily and quickly isolate the lowest with X & -X.
And on nearly all (2sC) machines nowadays a signed one as well.

- David.Thompson1 at worldnet.att.net