clean method to read bit position?

[Scott Kelley]

From a byte containing only 1 bit, I need to find the number representing
the bit position.

Example:
00010000 = 4
00000001 = 0

Is there a simpler method than looping?

Thanks,
Scott Kelley

 

[Jens.Toerring]

From a byte containing only 1 bit, I need to find the number representing
the bit position.

Example:
00010000 = 4
00000001 = 0

Is there a simpler method than looping?

Depends on what you call "simpler". You could use a lookup table, i.e.
an array with 256 elements (assuming your byte is 8 bits long) where
at index 1 0 is stored, at index 2 1, at index 4 2 etc. Now use your
byte as the index and you get the bit position. By putting a number
larger than 7 into all unused slots you even have a simple and fast
check if there's really only a single bit set in that byte...

Regards, Jens

 

[Dan Pop]

From a byte containing only 1 bit, I need to find the number representing
the bit position.

Example:
00010000 = 4
00000001 = 0

Is there a simpler method than looping?

Dumb looping is by far the simplest method. And for 8-bit numbers,
probably also the fastest. For larger numbers, you may want to consider
a binary search.

Dan

 

[xarax]

Depends on what you call "simpler". You could use a lookup table, i.e.
an array with 256 elements (assuming your byte is 8 bits long) where
at index 1 0 is stored, at index 2 1, at index 4 2 etc. Now use your
byte as the index and you get the bit position. By putting a number
larger than 7 into all unused slots you even have a simple and fast
check if there's really only a single bit set in that byte...

That is clearly a very fast technique, but remember that
a some implementations have a CHAR_BIT thing that indicates
more than 8 bits in a "char". A "char" is traditionally used
to represent an 8-bit byte, but it may be different on a
Deathstation implementation. You will likely want to qualify
with "unsigned char" to be sure that the value is not
sign-extended when promoted to an int for indexing the array.

Thus, you may have to use masking and shifting to force
an 8-bit value for the 256-element array index.

If you want to isolate the rightmost 1 bit, you could
use something like (ASSUMING TWOS-COMPLEMENT representation):

signed int foo = 12;
signed int right_bit_of_foo = (foo & -foo); /* this is 4 */

When using a twos-complement implementation (i.e., not
a Deathstation implementation), bit-wise AND of an integer
with its twos-complement isolates the rightmost 1 bit.

From there, you can use shifting and masking to find the
rightmost nonzero 8-bit value for indexing into the array.

2 cents worth. Your mileage may vary.


--
----------------------------
Jeffrey D. Smith
Farsight Systems Corporation
24 BURLINGTON DRIVE
LONGMONT, CO 80501-6906
http://www.farsight-systems.com
z/Debug debugs your Systems/C programs running on IBM z/OS!
Are ISV upgrade fees too high? Check our custom product development!

 

[gabriel]

Example:
00010000 = 4
00000001 = 0
Is there a simpler method than looping?

Not for what you want, looping is the best answer. Think of what you
have to do above to get 4 with a single formula:

log(00010000[binary]) / log(2[decimal]) - 1 = 4

That's very expensive operations! It much easier to compare the suspect
value to powers of two one by one.

 

[ESOJAY]

From a byte containing only 1 bit, I need to find the number representing
the bit position.

Example:
00010000 = 4
00000001 = 0

Is there a simpler method than looping?

Thanks,
Scott Kelley

My preferred but CPU intensive solution is (int)( log(byte)/log (2) ) ;

Esojay

 

[pete]

From a byte containing only 1 bit, I need to find the number representing
the bit position.

Example:
00010000 = 4
00000001 = 0

Is there a simpler method than looping?

Bit 0 is set in 1
Bit 1 is set in 2
Bit 2 is set in 4
Bit 3 is set in 8
Bit 4 is set in 16
Bit 5 is set in 32
Bit 6 is set in 64
Bit 7 is set in 128

/* BEGIN bit_pos.c */

#include <stdio.h>

int bit_pos(unsigned char byte)
{
int pos;
unsigned char mask;

if (byte == 1) return 0;
if (byte == 2) return 1;
if (byte == 4) return 2;
if (byte == 8) return 3;
if (byte == 16) return 4;
if (byte == 32) return 5;
if (byte == 64) return 6;
if (byte == 128) return 7;
pos = 7;
mask = 128;
do {
++pos;
mask <<= 1;
} while (mask != byte);
return pos;
}

int main(void)
{
unsigned char byte;

byte = 0;
do {
if (byte != 0 && (byte & byte - 1) == 0) {
printf("Bit %d is set in %d\n", bit_pos(byte), byte);
}
} while (++byte != 0);
return 0;
}

/* END bit_pos.c */

 

[Ben Pfaff]

Dumb looping is by far the simplest method. And for 8-bit numbers,
probably also the fastest. For larger numbers, you may want to consider
a binary search.

I imagine that a 256-entry lookup table is faster than dumb
looping for 8-bit numbers.

 

[Dan Pop]

I imagine that a 256-entry lookup table is faster than dumb
looping for 8-bit numbers.

Hard to say. If the table is not in the cache when you need it...
And to bring it in cache, the CPU may have to flush some other useful
data...

Dan

 

[Sean Kenwrick]

Bit 0 is set in 1
Bit 1 is set in 2
Bit 2 is set in 4
Bit 3 is set in 8
Bit 4 is set in 16
Bit 5 is set in 32
Bit 6 is set in 64
Bit 7 is set in 128

/* BEGIN bit_pos.c */

#include <stdio.h>

int bit_pos(unsigned char byte)
{
int pos;
unsigned char mask;

if (byte == 1) return 0;
if (byte == 2) return 1;
if (byte == 4) return 2;
if (byte == 8) return 3;
if (byte == 16) return 4;
if (byte == 32) return 5;
if (byte == 64) return 6;
if (byte == 128) return 7;
pos = 7;
mask = 128;
do {
++pos;
mask <<= 1;
} while (mask != byte);
return pos;
}

int main(void)
{
unsigned char byte;

byte = 0;
do

if (byte != 0 && (byte & byte - 1) == 0) {
printf("Bit %d is set in %d\n", bit_pos(byte), byte);
}
} while (++byte != 0);
return 0;
}

/* END bit_pos.c */

I prefer a switch statement to 'if's (cos it's easier to type):

switch(byte){
case 1: return 0;
case 2: return 1;
case 4: return 2;
...
default: return -1;
}

Sean

 

[Horst Kraemer]

My preferred but CPU intensive solution is (int)( log(byte)/log (2) ) ;

Then I should definitely avoid software written by you ;-)

On my system (gcc 3.3.1 cygwin)

(int) (log(8)/log(2))

yields 2.

 

[Scott Kelley]

I prefer a switch statement to 'if's (cos it's easier to type):

switch(byte){
case 1: return 0;
case 2: return 1;
case 4: return 2;
...
default: return -1;
}

Sean

Were you being literal with the above statement? Cannot find any reference
to a switch statement being used to return a value. All info I find
discusses only the form I'm used to:

case 1: {x = 0; break;}
case 2: {x = 1; break;}

If it can be used as you show, that would be very useful to me.

Scott Kelley

 

[pete]

Sean Kenwrick wrote:

I prefer a switch statement to 'if's (cos it's easier to type):

switch(byte){
case 1: return 0;
case 2: return 1;
case 4: return 2;
...
default: return -1;
}

/* BEGIN bit_pos.c */

#include <stdio.h>

int bit_pos(unsigned char byte)
{
int pos = 7;
unsigned char mask = 1u << 7;

do {
++pos;
mask <<= 1;
} while (mask != byte);
return pos;
}

#define bit_pos(A) \
((A) == 1u << 0 ? 0 \
: (A) == 1u << 1 ? 1 \
: (A) == 1u << 2 ? 2 \
: (A) == 1u << 3 ? 3 \
: (A) == 1u << 4 ? 4 \
: (A) == 1u << 5 ? 5 \
: (A) == 1u << 6 ? 6 \
: (A) == 1u << 7 ? 7 \
: (bit_pos)(A))

int main(void)
{
unsigned char byte;

byte = 1;
do {
printf("Bit %d is set in %d\n", bit_pos(byte), byte);
byte <<= 1;
} while (byte != 0);
return 0;
}

/* END bit_pos.c */

 

[Ben Pfaff]

Were you being literal with the above statement? Cannot find any reference
to a switch statement being used to return a value. All info I find
discusses only the form I'm used to:

case 1: {x = 0; break;}
case 2: {x = 1; break;}

If it can be used as you show, that would be very useful to me.

A return statement can be used within a switch statement just as
it can be used in any other context. I hope you don't think that
it causes the switch statement itself to have a value; rather, it
returns a value from the function just as in any other context.

 

[Scott Kelley]

A return statement can be used within a switch statement just as
it can be used in any other context. I hope you don't think that
it causes the switch statement itself to have a value; rather, it
returns a value from the function just as in any other context.

Do you mean that it would be used as follows?

char myfunction(char);
.. . .

bit = myfunction(x);

char myfunction(byte) {
switch(byte){
case 1: return 0;
case 2: return 1;
case 4: return 2;
...
default: return -1;
}
}

 

[Ben Pfaff]

Do you mean that it would be used as follows?

char myfunction(char);
. . .

bit = myfunction(x);

char myfunction(byte) {
switch(byte){
case 1: return 0;
case 2: return 1;
case 4: return 2;
...
default: return -1;
}
}

Yes (although I probably would not use `char' as the return
type).

 

[Jens.Toerring]

Do you mean that it would be used as follows?

char myfunction(char);
. . .

bit = myfunction(x);

char myfunction(byte) {
switch(byte){
case 1: return 0;
case 2: return 1;
case 4: return 2;
...
default: return -1;
}
}

Yes, definitely. There's nothing wrong with that. It's not different
from e.g. returning from within a for loop. You can even call exit()
from within a switch;-)
Regards, Jens

 

[Peter Nilsson]

From a byte containing only 1 bit, I need to find the number representing
the bit position.

Example:
00010000 = 4
00000001 = 0

Is there a simpler method than looping?

Define simpler? The following is O(1) for 8-bits...

#include <stdio.h>

int main(void)
{
static int table[8] = { 7, 0, 5, 1, 6, 4, 3, 2 };
unsigned x;

for (x = 1; x < 256; x <<= 1) /* x: 2**[0..7] */
{
printf("0x%02X: ", x);
printf("bit %d\n", table[((x * 0x3A) >> 5) & 7]);
}

return 0;
}

Of course, the (hashing) method is not likely to be practical for such
narrow integers. BTW, it's based on...

http://groups.google.com/[email protected]

 

[Chris Torek]

[Someone wrote] ...

Were you being literal with the above statement? Cannot find any reference
to a switch statement being used to return a value. All info I find
discusses only the form I'm used to:

case 1: {x = 0; break;}
case 2: {x = 1; break;}

I suspect you think that switch/case constructs are quite restricted
(which is often true in other languages). C is a bit lower level
than that -- a switch is just a goto in disguise:

volatile unsigned char *dev;
unsigned char *mem;
...
i = n / 8;
switch (n % 8) {
do {
*dev = *mem++;
case 7: *dev = *mem++;
case 6: *dev = *mem++;
case 5: *dev = *mem++;
case 4: *dev = *mem++;
case 3: *dev = *mem++;
case 2: *dev = *mem++;
case 1: *dev = *mem++;
case 0: ;
} while (i-- != 0);
}

This construct, called "Duff's Device" after Tom Duff (see the
FAQ), is entirely valid Standard C. The "switch" is just a goto,
and each "case" label is just a target label. (The FAQ's version
is slightly different -- I looked it up after typing in the above.)

The only "magic" about switch/case is that a case "looks upwards"
in enclosing brace scope blocks to find the innermost enclosing
"switch" statement, and places the appropriate "if (switch_expr ==
this_case_constant) goto here" up there. (Old non-optimizing
C compilers actually implemented this by compiling:

switch (expr) {
...
}

as if it were:

tmp = expr;
goto just_past_end_of_switch;
...
goto around;
just_past_end_of_switch:
if (tmp == first_value) goto first_label;
if (tmp == second_value) goto second_label;
...
if (tmp == last_value) goto last_label;
if (there was a default) goto default_label;
around:

This allows the compiler to "forget" the code in between, and
remember only the <value,label> pairings. The <value,label>
pairs can also be compared more efficiently than with a straight
sequence of "if"s; e.g., if the table is dense this turns into:

if (tmp >= first_value && tmp <= last_value)
goto label[tmp - first_value];
if (there was a default)
goto default_label;
around:

and in other cases the compiler could generate an inline
binary search.)

The fact that "case" labels are really just goto-labels is
also the (or at least "a") logical reason behind the requirement
for a "break" statement if you did not want to fall through
from one case to the next. Just as:

if (x == 1) goto label;
f();
label:
g();

executes g() even when x == 2, so does a switch/case.

 

[Peter Nilsson]

Yes (although I probably would not use `char' as the return
type).

Ben's referring to situations where plain char is unsigned and constructs like...

if (myfunction(blah) == -1)

....may not work as expected, i.e. UCHAR_MAX is not -1.