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

electroRF · Dec 11, 2013

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 · Dec 11, 2013

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

Pseudo code.

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 · Dec 11, 2013

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 · Dec 11, 2013

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 · Dec 11, 2013

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 · Dec 11, 2013

Tried this:

Code:

#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?

Code:

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 · Dec 11, 2013

You can test quick compiles here:

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

Pommie · Dec 11, 2013

electroRF said:
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 · Dec 11, 2013

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 · Dec 11, 2013

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 · Dec 11, 2013

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 · Dec 12, 2013

Pommie said:
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 · Dec 12, 2013

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

electroRF · Dec 12, 2013

great link T!
Thanks a lot!

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

Pommie · Dec 12, 2013

electroRF said:
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 · Dec 15, 2013

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

Is this C or Assembly?

misterT · Dec 16, 2013

killivolt said:
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 · Dec 16, 2013

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

Pommie · Dec 16, 2013

NorthGuy said:
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 · Dec 16, 2013

Pommie said:
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

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

Member

Well-Known Member

Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Member

Well-Known Member

Member

Member

Well-Known Member

Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Similar threads

Privacy & Transparency

Privacy & Transparency