Reorder numpy array to new bitlength elements without loop

Question

If I have a numpy array with elements each representing e.g. a 9-bit integer, is there an easy way (maybe without a loop) to reorder it in a way that the resulting array elements each represent a 8-bit integer with the "lost bits" at the end of the previous element getting added at the beginning of the next element? for example to get the following

np.array([0b100111000, 0b100101100, 0b110011100, 0b110010100])  # initial array in binarys
# convert to
np.array([0b10011100, 0b01001011, 0b00110011, 0b10011001, 0b01000000])  # resulting array

I hope it is understandable what I want to archive. Additional info, I don't know if this makes any difference: All of my 9-bit numbers start with the msb beeing 1 (they are bigger than 255) and the last two bits are always 0, like in the example above. The arrays I want to process are much bigger with thousands of elements.

Thanks for your help in advance!

edit:

my current (complicated) solution is the following:

import numpy as np
def get_bits(data, offset, leng):
    data = (data % (1 << (offset + leng))) >> offset
    return data

data1 = np.array([0b100111000, 0b100101100, 0b110011100, 0b110010100])
i = 1
part1 = []
part2 = []
for el in data1:
    if i == 1:
        part2.append(0)
    part1.append(get_bits(el, i, 8))
    part2.append(get_bits(el, 0, i)<<(8-i))
    if i == 8:
        i = 1
        part1.append(0)
    else:
        i += 1
if i != 1:
    part1.append(0)
res = np.array(part1) + np.array(part2)

Nice, I could try to improve mine with cycle stuff or something to adjust to any size but it look like Mad Physicist got you a much better solution — Copperfield
– Copperfield, Commented Sep 26, 2021 at 19:04
@Copperfield Yes, I think Mad Physicist has outperformed our solutions by far. But thanks for your help! — Phaneroptera
– Phaneroptera, Commented Sep 27, 2021 at 9:27

Mad Physicist · Accepted Answer · 2021-09-27 09:12:12Z

3

You can do it in two steps with np.unpackbits and np.packbits. First turn your array into a little-endian column vector:

>>> z = np.array([0b100111000, 0b100101100, 0b110011100, 0b110010100], dtype='<u2').reshape(-1, 1)
>>> z.view(np.uint8)
array([[ 56,   1],
       [ 44,   1],
       [156,   1],
       [148,   1]], dtype=uint8)

You can convert this into an array of bits directly by unpacking. In fact, at some point (PR #10855) I added the count parameter to chop of the high zeros for you:

>>> np.unpackbits(z.view(np.uint8), axis=1, bitorder='l', count=9)
array([[0, 0, 0, 1, 1, 1, 0, 0, 1],
       [0, 0, 1, 1, 0, 1, 0, 0, 1],
       [0, 0, 1, 1, 1, 0, 0, 1, 1],
       [0, 0, 1, 0, 1, 0, 0, 1, 1]], dtype=uint8)

Now you can just repack the reversed raveled array:

>>> u = np.unpackbits(z.view(np.uint8), axis=1, bitorder='l', count=9)[:, ::-1].ravel()
>>> result = np.packbits(u)
>>> result.dtype
dtype('uint8')
>>> [bin(x) for x in result]
['0b10011100', '0b1001011', '0b110011', '0b10011001', '0b1000000']

If your machine is native little endian (e.g., most intel architectures), you can do this in a one-liner:

z = np.array([0b100111000, 0b100101100, 0b110011100, 0b110010100])
result = np.packbits(np.unpackbits(z.view(np.uint8), axis=1, bitorder='l', count=9)[:, ::-1].ravel())

Otherwise, you can do z.byteswap().view(np.uint8) to get the right starting order (still one liner though, I suppose).

edited Sep 27, 2021 at 9:12

answered Sep 26, 2021 at 18:37

Mad Physicist

116k29 gold badges202 silver badges292 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Phaneroptera Over a year ago

that does the trick, thank you very much!

Mad Physicist · Accepted Answer · 2021-09-27 11:10:39Z

It's been bugging me that np.packbits and np.unpackbits are inefficient, so I came up with a bit twiddling answer.

The general idea is to work it like any resampler: you make an output array, and figure out where each piece of the output comes from in the input. You have N elements of 9 bits each, so the output is:

data = np.array([0b100111000, 0b100101100, 0b110011100, 0b110010100])
result = np.empty(np.ceil(data.size * 9 / 8).astype(int), dtype=np.uint8)

Every nine output bytes have the following pattern relative to the corresponding eight input bytes. I use {...} to indicate the (inclusive) bits in each input integer:

result[0] =              data[0]{8:1}
result[1] = data[0]{0:0} data[1]{8:2}
result[2] = data[1]{1:0} data[2]{8:3}
result[3] = data[2]{2:0} data[3]{8:4}
result[4] = data[3]{3:0} data[4]{8:5}
result[5] = data[4]{4:0} data[5]{8:6}
result[6] = data[5]{5:0} data[6]{8:7}
result[7] = data[6]{6:0} data[7]{8:8}
result[8] = data[7]{7:0}

The index of result (call it i) is really given modulo 9. The index into data is therefore offset by 8 * (i // 9). The lower portion of the byte is given by data[...] >> (i + 1). The upper portion is given by data[...] & ((1 << i) - 1), shifted left by 8 - i bits.

That makes it pretty easy to come up with a vectorized solution:

i = np.arange(result.size)
j = i[:-1]
result[i] = (data[8 * (i // 9) + (i % 9) - 1] & ((1 << i % 9) - 1)) << (8 - i % 9)
result[j] |= (data[8 * (j // 9) + (j % 9)] >> (j % 9 + 1)).astype(np.uint8)

You need to clip the index of the low portion because it may go out of bounds. You don't need to clip the high portion because -1 is a perfectly valid index, and you don't care which element it accesses. And of course numpy won't let you OR or add int elements to a uint8 array, so you have to cast.

>>> [bin(x) for x in result]
['0b10011100', '0b1001011', '0b110011', '0b10011001', '0b1000000']

This solution should be scalable to arrays of any size, and I wrote it so that you can work out different combinations of shifts, not just 9-to-8.

Beside beeing faster this solution is also better because it seems to be more compatible!

Copperfield · Accepted Answer · 2021-09-24 23:42:21Z

1

I think I understood most of what you want, and given that you can do bit operation with numpy arrays in which case you get the desire bit operation element wise if do it with two array (or the same for all if it is an array vs a number), then you need to construct the appropriate arrays to do the thing, so something like this

>>> import numpy as np
>>> x = np.array([0b100111000, 0b100101100, 0b110011100, 0b110010100])
>>> goal=np.array([0b10011100, 0b01001011, 0b00110011, 0b10011001, 0b01000000])
>>> x
array([312, 300, 412, 404])
>>> goal
array([156,  75,  51, 153,  64])
>>> shift1 = np.array(range(1,1+len(x)))
>>> shift1
array([1, 2, 3, 4])
>>> mask1  = np.array([2**n -1 for n in range(1,1+len(x))])
>>> mask1
array([ 1,  3,  7, 15])
>>> res=((x>>shift1)|((x&mask1)<<(9-shift1)))&0b11111111
>>> res
array([156,  75,  51, 153], dtype=int32)
>>> goal
array([156,  75,  51, 153,  64])
>>>

I don't understand why your goal array have one extra element, but the above operation give the others numbers, and adding one extra is not complicated, so adjust as necessary.

Now for explaining the ((x>>shift1)|((x&mask1)<<(9-shift1)))&0b11111111

First I notice you do a bigger shift by element, that is simple

>>> x>>shift1
array([156,  75,  51,  25], dtype=int32)
>>> 
>>> list(map(bin,x>>shift1))
['0b10011100', '0b1001011', '0b110011', '0b11001']
>>>

We also want to catch the bits that would be lose with the shift, with an and with an appropriate mask we get those

>>> x&mask1
array([0, 0, 4, 4], dtype=int32)
>>> list(map(bin,mask1))
['0b1', '0b11', '0b111', '0b1111']
>>> list(map(bin,x&mask1))
['0b0', '0b0', '0b100', '0b100']
>>>

then we right shift that result by the complementary amount

>>> 9-shift1
array([8, 7, 6, 5])
>>> ((x&mask1)<<(9-shift1))
array([  0,   0, 256, 128], dtype=int32)
>>> list(map(bin,_))
['0b0', '0b0', '0b100000000', '0b10000000']
>>>

then we or both together

>>> (x>>shift1) | ((x&mask1)<<(9-shift1))
array([156,  75, 307, 153], dtype=int32)
>>> list(map(bin,_))
['0b10011100', '0b1001011', '0b100110011', '0b10011001']
>>>

and finally we and that with 0b11111111 to keep only the 8 bit we want

Additionally, you mention that the last 2 bit are always zero, then a more simple solution is simple shift it by 2, and to recover the original just shift in back in the other direction

>>> x
array([312, 300, 412, 404])
>>> y = x>>2
>>> y
array([ 78,  75, 103, 101], dtype=int32)
>>> y<<2
array([312, 300, 412, 404], dtype=int32)
>>>

edited Sep 24, 2021 at 23:42

answered Sep 24, 2021 at 23:25

Copperfield

8,6353 gold badges26 silver badges32 bronze badges

2 Comments

Phaneroptera Over a year ago

Thank you very much for that answer, I needed some time to try it. I figured out it won't work for more than 8 elements. I have a much bigger array to process in reality, but it is my bad that I didn't mention that in the question.The problem is the difference of the resulting array with the initial array, since every 8 elements of the initial array the result array needs an extra element. Because of that I don't think it is possible to implement a general solution with the algorithm you suggested. Anyway, the idea was great!

Mad Physicist Over a year ago

You were a couple of modulo operators from a totally generic solution. I posted a second answer demonstrating this.

Collectives™ on Stack Overflow

Reorder numpy array to new bitlength elements without loop

3 Answers 3

1 Comment

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related