Performing right shift and bit masking on binary fraction in python

0
votes

I am looking for a way in python to perform right shift and bit masking on a binary number which has a fraction part as well. For e.g., if there are 1 integer and 2 fraction bits in the number, then number 0b101 corresponds to 1.25 in decimal. First, I want to know the pythonic way to represent this number in python.

Second, I want to perform 1 right shift on this number (0b101>>1) so that the resultant number will be 0b010 which will be 0.5 in decimal. Is there an intrinsic and pythonic way in python to perform this operation. Similarly, how to mask and get a specific bit from the binary number?

Presently, for shift I am multiplying the number by 2**-x, x is the number of right shifts. I cannot think a similar operation I can perform for bit mask.

2
pythonbinarybit-shiftbitmask
I don't think you should be attempting bitmask operations on floating-point numbers. It is true that 0b101 is one way to represent 1.25 on paper but that is not how it is stored in memory, because the leading 1-bit is implied. Your operation will fail on unnormalized floating point numbers unless you check for that first. Your code will be very hard to read and probably slower than multiplying by powers of 2. There are probably several other good reasons why not. - BoarGules
Operator >> is the python right shift operator. - quamrana
@BoarGules for my project I want to extract the particular bit present within fraction part. Even though I cannot perform the available bit-operators in python, I was looking for a way to extract the bit. Only way I could find was to first convert the number to integer by multiplying it by 2**number_of_fraction_bits, and then extracting the required bit. Don't know if there is a better way to do this. - Gaurav Srivastava
I'd encapsulate everything in a class. Do you get the same answers to everything if you only work with integers, then divide by 2^n afterwards (where n is the number of "floating point bits")? - Kenny Ostrom
@KennyOstrom Yes I do get same value as right shifted operation when I divide by 2^n. - Gaurav Srivastava

2 Answers

2
votes

If you really must get directly at the internal representation of a float you can use struct, like this:

>>> import struct
>>> a = 1.25
>>> b = struct.pack('>d',a) 
>>> b
b'?\xf4\x00\x00\x00\x00\x00\x00'  # the ? means \x3f, leftmost 7 bits of exponent
>>> a.hex()
'0x1.4000000000000p+0'

You can mask the bit you want out of the bytestring that struct.pack() returns.

[edit] The question mark representing \x3f is because the default output representation of a bytestring is a string and Python will where possible show an ascii character, not two hex digits.

[edit] This representation is in principle platform-dependent, but in practice it isn't, because virtually every computer (even IBM mainframes nowadays) has a floating-point processor that uses this format.

Finding out which bit you want may be something of a challenge.

>>> c = struct.pack('>d',a/2)
>>> c
b'?\xe4\x00\x00\x00\x00\x00\x00'
>>> (a/2).hex()
'0x1.4000000000000p-1'

As you can see, division by 2 is not quite the simple one-bit shift to the right that your question seems to suggest you are expecting. In this case, the division by 2 has decremented the exponent by 1 (from 0x3ff to 0x3fe; 1023 to 1022) and left the bit pattern of the fraction (0x4000) unchanged. The exponent appears large because it is biased by 1023.

The main difficulties are

  1. Sign, exponent and fraction don't align to byte boundaries, but to nybble boundaries (sign plus exponent: 12 bits; fraction: 52 bits)
  2. The number is normalized so that it has no leading zeroes (much as scientific notation in decimal is normalized so that it has no leading zeroes) and, since everyone knows it's there, the leading 1 is not stored.

I can recommend the Wikpedia article on this subject: it has lots of useful examples.

But I suspect that you don't really want to get at the internal representation of a float. Instead, you want a fixed-point binary class, without pesky binary exponents, that works much the same as you would do it on paper, and where division by a power of 2 really does reflect as a shift of so many bits to the right.

Depending on how much work you want to put into it, you could do this by defining a FixedBinary class as a subclass of numbers.Real, with the integer portion internally represented by one int and the fractional component by another int, and the sign by a third int, so that 1.25 would be represented as (1, int(0.25 * 65536), +1) (or some other power of 2).

This also shows you the simplest way to get a bit representation of your fraction.

[edit] I recommend storing the sign separately. You could store it in the integer portion, or the fraction, or both, but all have disadvantages.

  1. If you store it in the sign of the fraction, the twos-complement representation of negative integers will give you difficulty when you want to mask your bits.
  2. If you don't store it in the sign of the fraction there will be no way to represent -0.5.
  3. If you don't store it in the sign of the integer portion there will be no way to represent -1.0.

A multiplicand of 65536 will give you 4 decimal digits of accuracy. You can increase it if you want more. I also recommend that you store your fraction in the rightmost bits and simply ignore the leftmost bits. In other words, be content with the binary point being in the middle of the int, don't insist on it being on the left. That is because you will need headroom to the left of the binary point when you do multiplication.

Implementing your own numeric class is a considerable amount of work, though.

1
votes

You can work using fxpmath.

Info about this package is at: https://github.com/francof2a/fxpmath

For your example:

from fxpmath import Fxp

x = Fxp('0b0101', signed=True, n_word=4, n_frac=2)

print(x)

y = x >> 1

print(y)

# example of AND mask
z = x & Fxp('0b0110', signed=True, n_word=4, n_frac=2)
print(z.bin())

outputs:

1.25
0.5
0100