How can I get a bit's position in the int?

[roadrunner17]

Is there a way to get a bit's position in a datatype? For example, if int var1 = 64 how can I know that it is in position 7, or if var1 = 16 that it is in position 5, or any position in the 32 bit word (there will only be 1 bit set at a time)?

I would like to get this preferably without calling a squareroot function (hopefully using just bit operators). Computing this index needs to be as fast as possible as I will have to do this countless times on 384 bits at a time.

Thanks for your help,

[Yves M]

Is there always only one bit set in your int ?

A kind of easy way to do this would be to use the following (it is probably not the fastest, but can be OK if the compiler optimizes properly).

 int var1;
 int i;

 i = 0;
 while (var1 != 0) {
   var1>>= 1;
   i++;
 }

Then i will be the bit position + 1 or 0 if var1 was zero already.

There is definitely a way to do this faster in assembler, but I can't remember all the instructions :/
(something like sar ax, 1 and then test for overflow)

[roadrunner17]

Thanks for the reply, I thought about doing this but it involves potentially looping 32 times for each int.

In this particular function I'm trying to write, I like to get the position of all the bits set with an int, i perform a bit operation that will isolate each bit 1 at a time. The loop that does this will execute once for each bit set.

I guess shifting in a loop is the only way to do this. Is there a way to use a lookup table, other than creating an array of 4294967295 values. :-)


Thanks again.

[Yves M]

Ok, here is some "optimized" assembler code for doing this (x86):
eax contains var1 and ecx contains i and hence the result. [I updated this to eliminate one test]

   xor ecx, ecx
   mov eax, var1
   test eax, eax
   je label_end
label_loop:
   inc ecx
   sar eax, 1
   jnz label_loop
label_end:
   mov i, ecx

What are you trying to do with the bits that are set ? Most of the answer will depend on this....

Say you want to set booleans... Then you can use the & operator and a lot of if statements (or triadics)...

bBitOne = (var1 & 0x00000001 ? TRUE : FALSE);
bBitTwo = (var1 & 0x00000002 ? TRUE : FALSE);
...

Or if you have the booleans in an array, you could use a loop

int i;
unsigned long ulbitpos:

ulbitpos = 1;
for (i = 0; i < 32; i ++) {
  bBit[i] = (var1 & ulbitpos ? TRUE : FALSE);
  ulbitpos <<= 1;
}

[Yves M]

Originally posted by roadrunner17
Thanks for the reply, I thought about doing this but it involves potentially looping 32 times for each int.

Well that would not really be that slow :/

The assembler version takes 5785 microseconds for 65536 times on my machine.

Unrolling the loop brings that down to 4010 microseconds

[Nikolai Borissov]

Here is a solution without loop. Hope it will be faster, but you should verify anyway.

inline int get_int_1_pos(int i)
{ int n=-1;
  if(i&0xffff0000) {n+=16;i>>=16;};
  if(i&0x0000ff00) {n+=8;i>>=8;};
  if(i&0x000000f0) {n+=4;i>>=4;};
  if(i&0x0000000c) {n+=2;i>>=2;};
  return n+i;
}

[Yves M]

sneaky, the old divider and conquer trick

Oh, and yes it will definitely be much faster than my loops

[AnthonyMai]

Yves M:

Do NOT show off any assembly code if you don't know assembly code. This won't help you pass any job interview :-)

Your "assembly" code easily takes 100 times more CPU cycles than it needs to get the result the OP wants. Then, what's your point in writting assembly code?

To find position of the first none zero bit of a 32 bits integer, counting either from left hand (MSB) or right hand(LSB), there are two single assembly instruction for this purpose:

BSF
or BSR

Now, as a homework assignment, go figure out how to do it using BSF or BSR. Keep in mind, no more than 3 lines of code.

[cup]

BSF/BSR/BTC/BTR only exist from 386 onwards. Those of us, like myself who use geriatric 286s on DOS are unable to use these instructions.

[Yves M]

AnthonyMai,

DO NOT CRITICIZE when you don't have a valid reason for doing it. I have not stated that I'm an assembly guru.

The point you make about using BSF or BSR is valid, so just say that. Anyways, it's no likely that I'll ever want a job as an assembly programmer anyways ;-)

cup, if I were using a 286, I couldn't use eax et al (I guess, or is a 286 also 32 bit ?)

[cup]

Yes EAX is also 32 bit and 386 upwards.

286s are strange beasties. The PCs only ever used them in 8086 mode so the 286 mode was never exploited except in RMX, which is an Intel OS.

386 added a lot to the instruction set: bit arrays, modifers etc. It even has stuff for adding breakpoints in ROM.

[Yves M]

And just exactly why do have to keep on using a 286 ?

[cup]

Home project - it is a control system that waters the garden and controls the air flow in the greenhouse. Nobody will pinch an old 286: you can leave it in the shed for years and know it is perfectly safe.

[Yves M]

Good point

[edit :

For roadrunner, here is the assembler code that finds the least significant bit set in var1

BSF ecx, var1
jnz  label_found
mov ecx, 0xFFFFFFFF
label_found:
mov i, ecx

Sorry, Anthony, you'll have to show me how to do it in three lines of code though

I guess you are thinking about something along the lines of :

mov ecx, 0xFFFFFFFF
BSF ecx, var1
mov i, ecx

But according to my assembler reference, if var1 is zero, then the contents of ecx are undefined :/ On my processor it seems to work though (Pentium III mobile), but I'm not sure that you can rely on the fact that ecx is not modified.

Oh, and yes, timing this gives me 270 microseconds for 65536 times. So that's a decent improvement
]

[AnthonyMai]

DO NOT CRITICIZE when you don't have a valid reason for doing it. I have not stated that I'm an assembly guru.

The point you make about using BSF or BSR is valid, so just say that. Anyways, it's no likely that I'll ever want a job as an assembly programmer anyways ;-)

Sorry for being a bit hash on you, but had you not criticize me before in no good way for no good reason, I would have said things nicer. Compare with other people, at least you are willing to write SOME assembly code some times.

I have not stated I am an assembly guru either. And I surely do not want a job as an assembly programmer. And surely I don't think there are still any pure assembly programming job around. But every C++/C programmer needs to know the correct way of how to speed things up here and there using the right assembly, when the needs raise. And raises often the needs indeed.

Controling garden hoses and air conditioning like CPU do does not require much CPU power so a 286 is more than needed. But since the OP wants somethiing as fast as possible I would assuming he is no longer using 286. I even have a pretty good guess exactly what his application is and why he needs speed.

But according to my assembler reference, if var1 is zero, then the contents of ecx are undefined :/ On my processor it seems to work though (Pentium III mobile), but I'm not sure that you can rely on the fact that ecx is not modified.

"Undefined" means it's never touched so it was left at an undefined value, meaning whatever ecx was before, it was left unchanged. So, yes, you can count on it that ecx is not modified if bsf or bsr find no set bit.

The original OP wants to determine the bit in a 384 bit data structure, not just a 32 bit integer. You should be able to do it in 6 lines of assembly code. I will let you pass the job interview if you do this homework correctly :-)