CODEWITHSUNDEEP
bit-manipulationbit
user3243499
user3243499

Reputation: 3151

How to calculate the set bit positions in a number?

If n = 100011 in binary, then I want to retrieve the positions of set bits which in this case are 1,5,6 when measured from left to right.

How to calculate such positions without literally checking for bit is zero or not by going to every bit position?

Upvotes: 0

Views: 2528

Answers (2)

user555045
user555045

Reputation: 64904

In the most common convention, a binary number is written in the order as a number in other common positional representations (decimal etc): with the least significant digit in the rightmost position. It also makes more sense to label that digit as "digit zero", so that the label of every digit corresponds with the exponent in the associated weight (eg bit 0 has weight 20=1 and so forth). This doesn't really matter, it's easy enough to re-number the digits, but it's usually easier to follow the conventions.

Since you asked

How to calculate such positions without literally checking for bit is zero or not by going to every bit position?

I will address that portion of the question. Checking the bits one by one is not completely disastrous however. Even for BigInts. The number of results could be as high as the number of bits anyway. For numbers known to be sparse, there is still not much that can be done - every bit has to be checked somehow because if any bit is ignored completely, that bit might have been set and we'd miss it. But in the context of a machine word, there are tricks, for example based on find-first-set.

Using the find-first-set function (or count trailing zeroes), the index of the set bit with the lowest index can be found in one step (if you accept this function as being one step, which is a reasonable assumption on most hardware, and in theory you can just define it to be one step), and then that bit can be removed so the next find-first-set will find the index of the next bit. For example:

while bitmask != 0:
    yield return find-first-set(bitmask)
    bitmask &= bitmask - 1 // remove lowest set bit

This is easy to adapt to BigInts, just do this on every limb of the number and add the appropriate offset.

Upvotes: 1

Juan
Juan

Reputation: 5589

To do that you use masks.

Each position from right to left is a power of two. For example 0101 is 1*2ˆ0 + 0*2ˆ1 + 1*2ˆ2 + 0*1ˆ3 = 1+0+4+0 = 5

Then to check if these two bits are on against a bytesToTest variable you AND with 5: byteToTest & 5 == 5

Given that 1 & 0 = 0 and 1 & 1 = 1

If bytesToTest is 1111 then 1111 & 0101 will give 0101
If bytesToTest is 1010 then 1010 & 0101 will give 0000

Following this reasoning for the particular case of 100011 To retrieve 1, 5, and 6 from left to right (the three ones set to 1)

The mask is: 1+2+32 = 35

With this information you should be able to define individual masks for each bit, test one by one, and be able to answer in which position you find bits that are on and in which bits that are off.

Upvotes: 1

Related Questions