Before we begin, please note that LSB means least significant bit
and not necessarily last (significant) set bit.
1.
Determine
if a number is even or odd
All odd
numbers share the interesting property that the LSB(least significant bit)
should always be 1. (why?)
>>>
bin(21)
'0b10101'
>>>
bin(33)
'0b100001'
>>>
bin(45)
'0b101101'
So, how
do we go about determining LSB of a number. The answer is we do not. At least
not directly. ANDing with 1, which is in effect 000000…1 provides the easy
answer. If the LSB is 1, we will get 1 else we get 0.
>>>
21 & 1
1
>>>
20 & 1
0
>>>
22 & 1
0
So much
for finding the LSB, but how do we find the MSB? Let’s first find the number of
bits set.
2.
Getting
all the bits from an int
If we can
get all the bits of an integer in the most ubiquitous data structure of Python,
namely list, then we can surely get LSB, MSB and any other bit that we may be
interested in. We can use list comprehension, the code is bit terse, so pay
attention.
[int(z)
for z in [y for y in bin(x)][2:]]
We store
the integer in x, convert it to binary and store the characters in a list. Then
we slice it using [2:] to remove the initial 0b. And finally convert everything
to int. Here is a sample run –
>>>
x = 21
>>>
[int(z) for z in [y for y in bin(x)][2:]]
[1, 0, 1,
0, 1]
Let’s get
LSB and MSB directly now –
>>>
[int(z) for z in [y for y in bin(x)][2:]][0]
1
>>>
[int(z) for z in [y for y in bin(x)][2:]][:]
[1, 0, 1,
0, 1]
>>>
[int(z) for z in [y for y in bin(x)][2:]][-1]
1
3.
Number
of bits set
In this
part, our goal is to find which all bits are 1. Carrying on with our code in
the previous section, we can apply another comprehension –
>>>
len([ k for k in [int(z) for z in [y for y in bin(x)][2:]] if k == 1] )
3
We apply
another comprehension, put a 1 in our new list if we encounter 1 in the old
list and take the length of the final list.
4.
Clearing
the last set bit, just insane!
In this
task we want to clear (make it 0) the last set bit. Again enumerating the bits in
a list the way we did in last two exercises is an option though not a smart
one. We can do better.
We note
that when we subtract 1 from a number it will compulsorily mean making the last
set bit to zero (because that’s where the 1 required for subtracting is going
to come from) and making all the zeros preceding it to 1. See this
>>>
bin (43)
'0b101011'
Last set bit is the LSB, so that’s where the action happens. Check out representation of 42.
>>>
bin (42)
'0b101010'
Now the
LSB is zero. And the last set bit is at second last position. That second last
position should turn into a zero. Let’s check out 41.
>>>
bin(41)
'0b101001'
5.
Power
of Two
To find
out if a given number is power of two or not, the standard trick is to apply x
& x-1
This
works (actually it doesn’t, but hang on for a second) because of what we saw in
the previous section about last set bit getting cleared. Power of 2 will be of
the format 1 …0000…000 , meaning there will be exactly one 1.
>>>
bin(256)
'0b100000000'
>>>
bin(1024)
'0b10000000000'
>>>
bin(255)
'0b11111111'
So when
we subtract one from a power of two, all the bits flip. Therefore, &
applied to the two integers will always produce 0.
>>>
256 & 255
0
FLAW:
This works (obviously) for positive numbers only. Remember the 2’s complement
we discussed in the last post. That’s what is preventing this formula from
being universal solution. Fortunately, a simple solution exists. If a number is
power of 2, so is it’s negative. So, we can begin the code by doing x = abs(x)
>>>
x = -21
>>>
x = abs(x)
>>>
x
21
And then
proceeding with solution.
6.
Number
of bits set – Kernigham way
Here we
keep clearing the LSB till we are left with a zero. The code is pretty simple.
>>>
def kerni(n):
... cnt = 0
... while(n):
... n &= n-1
... cnt += 1
... return cnt
...
>>>
kerni(21)
3
>>>
bin(21)
'0b10101'
No comments:
Post a Comment