Testing a Bit

One common requirement is to test if a particular bit is set or unset. Actually it is just as easy to test for any number of bits set or unset because the job is done using a mask. As before, if you create a mask with bits set corresponding to the bits you want to test then:

(value & mask) == 0 

is true if and only if all of the bits mask specifies are 0.

If all of the bits mask specifies are set to 1 then it returns mask. That is:

(value & mask) == mask

is true if all the bits mask specifies are set to 1.

Similarly:

(~value & mask) == 0

is true if and only if all the bits mask specifies are 1. Again, if the bits that mask specifies are set to 0 then the result is mask. This means you can use:

(~value & mask) == mask

to test for all the bits mask specifies being 0. Which form you use to test bits is up to you and the particular situation.

Usually you only want to test for a single bit and this makes the mask particularly simple. For example, if you test for the fifth bit to be a 0 using:

value = 0x1F
mask = 0x10
result = value & mask

then in this case the result is non-zero, 16 to be precise and the fifth bit is not 0. Perhaps confusingly, the result is 0 if and only if the fifth bit is 0.

Testing for a 1 can be even more confusing at first. For example:

value = 0x1F
mask = 0x10
result = ~value & mask

The mask tests the fifth bit in the value which is a 1 and so it is 0 in the negation. This gives a result of 0 and we conclude that that the fifth bit was set to 1. Again the result is 0 if and only if the fifth bit is a 1.

If you want a simple true or false result then you can avoid using the equality operator == by using the logical NOT operator. For example:

not(~value & mask)

is true if and only if all of the bits in value specified by the mask are 1 and false otherwise. Similarly:

not(value & mask) 

is true if and only if all of the bits in the value specified by the mask are 0 and false otherwise.

Bit Manipulation and Arithmetic

There is often a choice about how to perform a bit manipulation between logic and arithmetic. We have already seen that shift left and shift right are the same as multiplication or division by 2. What this means is that you can achieve the same result using bitwise operations or arithmetic.

This idea extends to other bit manipulations and you can spend some time trying to work out how to implement a given requirement as arithmetic. Sometimes the arithmetic approach is faster or more elegant. Often it is simply difficult for others to follow. For example, suppose you want to extract the lower four bits of a bit pattern. The simplest and most direct way is to use a mask:

bits = 0x1234
print(hex(bits & 0x000F))

This displays 0x4. You can achieve the same result using division, multiplication and subtraction. If you divide bits by 16 this is equivalent to a left shift of four giving 0x123. Multiplying this by 16 shifts it four bits to the right giving 0x1230. Subtracting this from the original value gives the bottom four bits i.e. 0x4. That is:

print(hex( bits - (bits//16)*16 ))

displays 0x4 and it is equivalent to using a mask, although a lot less efficient.

Arithmetic operations such as these are interesting because they work in other number bases with obvious adjustments. For example, if you want to extract the last four digits of a decimal number you can use:

dec = 12345678
print(dec - (dec//10000)*10000)

displays 5678. It works in exactly the same way, but there is no equivalent mask that can be used instead.

In general, division is a shift right, multiplication is a shift left, addition can be used to set zero bits and subtraction can be used to zero one bits.

Bit Manipulation As Art

This is just the start of the story. There are so many tricks and techniques of bit manipulation that it is an art form. You can find out about this by searching the web, but to give you a flavor of the sort of cleverness that goes on let’s count the number of bits that are set to one in the bit pattern. The best known solution is due to Brian Kernighan:

value = 0x55
count = 0
while(value):
    value &= value - 1
    count += 1
print(count)

Why does this work? The reason it counts the one bits can be understood by working out what happens the first time through the loop. If value ends in a 1 subtracting one removes it, e.g 101 – 1 = 100 ANDed with the original gives 100. If the value ends in a 0 then subtracting one has to borrow from higher order bits. In fact it borrows from the first high-order bit that is a 1. For example 100-1 has to borrow from the third bit in the pattern and the result is 011 which when ANDed with the 100 gives 000 and the loop ends. You can see that each time the subtraction causes a borrow from the first 1 bit to the right and this removes it from the value and the AND removes the lower-order bits that result from the subtraction – hence the loop repeats the number of times that there are one bits in the bit pattern.

If you don’t follow try it out for other bit patterns and marvel that anyone noticed that this works in general and provided a way to count bits.

This is very typical of creative bit manipulation – try not to waste too much time!

Summary

• The fundamental data entity is the bit pattern and it is up to the program and programmer to assign a meaning to any particular bit pattern.

• Hexadecimal (hex) makes specifying a bit pattern easier as each hex symbol corresponds to four binary bits.

• Number bases that are a power of 2 have the property that they are easier to convert to binary. The other base that is useful is octal which specifies three bits per symbol.

• The fact that Python uses unlimited precision integers, bignums, makes working with bit patterns different to the usually encountered fixed width bit patterns which are typically 16, 32 or 64 bits in size.

• The bitwise operators &, |, ^, ~ perform logical operations on pairs of bits.

• Negative numbers are a problem for bitwise operations because bignums are stored in sign-value representation and bitwise operations generally use two's complement representation.

• You cannot create a negative bignum using a binary value because you cannot set the sign bit. The only way is to use a negative sign.

• The not ~ operator is particularly difficult to understand unless you think of it as creating additional sign bits that are then trimmed back to a single sign bit.

• It is helpful to think in terms of masks to set and unset particular bits in a bit pattern.

• You can use a mask approach to testing if particular bits in a pattern are a zero or a one.

• The shift operators << and >> shift the bit pattern to the left and right. Left shifts move zeros into the left and right shift moves a copy of the sign bit into the most significant bit.

• An alternative to using logical bitwise operations is to use arithmetic. This is usually harder to understand, but it has the advantage of working in other number bases.

• Bit manipulation is an art form and you can spend many hours trying to find a clever and efficient way of doing any task.

Programmer's Python
Everything is Data

Is now available as a print book: Amazon

Contents

1. Python – A Lightning Tour
2. The Basic Data Type – Numbers
      Extract: Bignum
   
3. Truthy & Falsey
4. Dates & Times
      Extract Naive Dates
   
5. Sequences, Lists & Tuples
      Extract Sequences 
6. Strings
      Extract Unicode Strings
7. Regular Expressions
      Extract Simple Regular Expressions 
8. The Dictionary
      Extract The Dictionary 
9. Iterables, Sets & Generators
      Extract  Iterables 
10. Comprehensions
       Extract  Comprehensions 
11. Data Structures & Collections
       Extract Stacks, Queues and Deques
       Extract Named Tuples and Counters
12. Bits & Bit Manipulation
       Extract Bits and BigNum 
       Extract Bit Masks ***NEW!!!
13. Bytes
       Extract Bytes And Strings
       Extract Byte Manipulation 
14. Binary Files
       Extract Files and Paths 
15. Text Files
       Extract Text Files & CSV 
16. Creating Custom Data Classes
        Extract A Custom Data Class 
17. Python and Native Code
        Extract   Native Code
    Appendix I Python in Visual Studio Code
    Appendix II C Programming Using Visual Studio Code

<ASIN:1871962765>

<ASIN:1871962749>

<ASIN:1871962595>

<ASIN:B0CK71TQ17>

<ASIN:187196265X>

Related Articles

Creating The Python UI With Tkinter

Creating The Python UI With Tkinter - The Canvas Widget

The Python Dictionary

Arrays in Python

Advanced Python Arrays - Introducing NumPy

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.