nice "play with bits" question I'm struggling with

[electroRF]

Hi,
I ran into the following question.

you got a 4-byte number - num.

You're given additional number - count.

you need to return the index of the count'th '1' bit in num, from the right.

Example:
num = 0x05-30-21-04
count = 2

you need to return 8, because that is the index of num where the 2nd '1' occurs.

How would you do it without having a worst case of 32 'masking' operations to find the count'th bit?

Thanks

 

[Pommie]

I think I understand what you are asking and if so, try,

Pseudo code.

index=0
while num>0{
    index=index+1
    if num AND 0x80000000{
        count=count-1
        if count=0 then return index
    }// end if
    num=num*2
}// end while
// return -1 as no bit found

Mike.

 

[electroRF]

hi Pommie.

your code doesn't do what it should.

1. your code starts counting bits from left and not from right

2. your code it not efficient, it masks EVERY bit until it counts count '1' bits, and then return index.
this give worst case of 32 masking operations.

I'd like to make the code efficient.

 

[AtomSoft]

um why not shift and AND ?

Like:

num = 0x05302104
count = 2
byteToInspect = ((4-(count/8))-1) * 8

if byteToInspect > 23 byteToInspect 3
if byteToInspect > 15 & byteToInspect < 24 byteToInspect 2
if byteToInspect > 7 & byteToInspect < 16 byteToInspect 1
if byteToInspect >= 0 & byteToInspect < 8 byteToInspect 0

newVAL = (num >> byteToInspect) & (0x80>>count);

something like that?

EDIT: As a note or disclaimer... this is off the top of my head and may need fixes or changes ... but you should get it

 

[AtomSoft]

Wait so you are trying to RETURN the count on 1's only?

So the 2nd "1" or the 2nd bit whether its a 0 or 1

 

[AtomSoft]

Tried this:

#include <stdio.h>
#include <string.h>

main()
{
    printf("AtomSoftTech Test.\r\n" ); 
   
    int num = 0x05302104;
    int count = 2;
    int OneCount = 0;
    int index = 0;
    int x;
    int byteToInspect = 0;
   
    for (x = 0; x < 32; x++)
    {
        printf("x = %i\r\n", x );
        if((1<<x) & num) OneCount++;
        if(OneCount == 2) break;
    }
   
    printf("OneCount = %i\r\n", OneCount );
   
    index = x;
     
    printf("index = %i\r\n", index );
   
    if (index > 23) byteToInspect = 3;
    if ((index > 15) && (index < 24)) byteToInspect = 2;
    if ((index > 7) && (index < 16)) byteToInspect = 1;
    if ((index >= 0) && (index < 8)) byteToInspect = 0;
       
    int newVAL = ((num >> (byteToInspect*8))& 0x000000FF) & (0x80>>count);
   
    printf("NewVALUE = %i", newVAL );
}

got this result... are you looking for index?

AtomSoftTech Test.
x = 0
x = 1
x = 2
x = 3
x = 4
x = 5
x = 6
x = 7
x = 8
OneCount = 2
index = 8
NewVALUE = 32

 

[AtomSoft]

You can test quick compiles here:

http://www.compileonline.com/compile_c_online.php

 

[Pommie]

hi Pommie.

your code doesn't do what it should.
Yes it does.

1. your code starts counting bits from left and not from right
I work in little endian and you didn't state which. Also, in your example, the 8th bit from MSB is set whereas the 8th bit from LSB isn't.

2. your code it not efficient, it masks EVERY bit until it counts count '1' bits, and then return index.
this give worst case of 32 masking operations.
I don't see any other way to do it. Plus, efficient can mean less code rather than more speed. Again, you didn't state which.

I'd like to make the code efficient.
good luck with that.

See above,

Maybe you should practice stating your questions better. In the above we have no language mentioned and an ambiguous goal and example.

Mike.

 

[heydonms]

The only change that I would make to Pommie's code would be to use bitshift and inspect the carry bit. Which doesn't really change the code much, I just think it is more readable. I doubt it would actually be much (or any?) more efficient but technically you aren't performing any masking.

EDIT: I should say, I'm not sure this is possible with C (or at least, the overhead of doing it probably outweighs any possible saving from not having to do a separate bitmask operation). I do most of my uC coding in assembly where the carry flag is easily accessible.

 

[Pommie]

The carry flag is generally not available in high level languages, I also didn't shift as I wasn't sure of the language and most compilers will compile *2 as a bit shift anyway (or should). If C is chosen then one way to make it more efficient would to do a union so that the AND is done on a byte instead of an int32.

Mike.

 

[heydonms]

Agreed, if you are working in anything other than assembly then your way definitely makes sense.

The union is a good idea, I hadn't thought of that.

 

[electroRF]

See above,

Maybe you should practice stating your questions better. In the above we have no language mentioned and an ambiguous goal and example.

Mike.

Hi Mike,
Thanks a lot for your inputs.

It didn't think of the little endian vs big endian difference, and assumed without mentioning that i referred to big endian.

Why did you say that in my example, where num = 0x05-30-21-04, the 8th bit from the LS-bit is not set?
the two LS-Bytes are 0x21-04 (0x04 is the LS-Byte), so the 8th bit from the LS-bit is '1'.

 

[misterT]

https://www.hackersdelight.org/
https://www.hackersdelight.org/basics2.pdf

 

[electroRF]

great link T!
Thanks a lot!

btw, your name came into my mind when I wrote up this question here

 

[Pommie]

Hi Mike,
Thanks a lot for your inputs.

It didn't think of the little endian vs big endian difference, and assumed without mentioning that i referred to big endian.

Why did you say that in my example, where num = 0x05-30-21-04, the 8th bit from the LS-bit is not set?
the two LS-Bytes are 0x21-04 (0x04 is the LS-Byte), so the 8th bit from the LS-bit is '1'.

When we count positions it is customary to start at 1st. Yes, counting in programming starts at zero, however, I've not heard anyone call bit zero the zero'th bit, it's always the first bit. So, in 0x2104, the 8th bit is zero.

To be fair, there is great confusion over all these terms. The LSB is 2^0 and so could be called the zero'th bit. I just read your example and saw that only in little endian terms (and LSB or MSB =1st bit) did your example work.

Sorry for any confusion.

Did you get your function working?

Mike.

 

[killivolt]

https://www.hackersdelight.org/
https://www.hackersdelight.org/basics2.pdf

Is this C or Assembly?

 

[misterT]

Is this C or Assembly?

Neither. It is just logick. Computer science.. math. There are couple of small code snippets written in C and also some code written in assembly, but not very much at all.

 

[NorthGuy]

Many (most?) processors have a built-in command that does a search for a first set bit in a word.

 

[Pommie]

Many (most?) processors have a built-in command that does a search for a first set bit in a word.

I have never seen such an instruction. Do you know a particular processor with this ability?

Mike.

 

[NorthGuy]

I have never seen such an instruction. Do you know a particular processor with this ability?

BSF and BSR instructions in x86
FF1L and FF1R instructions in PIC24