Duplicate bits in a big numpy array

Question

I have a big numpy array (i.e. approx. 2 ** 32 positions) of 64-bit unsigned integers and I want to duplicate a single bit (can vary from 0 to 63) in every integer inside this array.

Example:

Input array: array([ 0, 5, 2, 7 ])
Position (right to left) to duplicate: 0

The input, in binary, is

000  101  010  111

After the operation, I want the bits as

0000 1011 0100 1111

Result: array([ 0, 11, 4, 15 ])

As stated, my arrays are huge, so I'd prefer to use the lowest number of temporary / auxiliar arrays.

I tried to find something close to it in Google or even Bit Twiddling Hacks with no luck.

Thanks in advance!

This is far too straightforward to end up in the bit twiddling hacks list: (x << 1) | (x & 1). — user2357112
– user2357112, Commented Apr 12, 2017 at 19:55
@user2357112 this only works when position = 0. Any bit can be duplicated. — Marco
– Marco, Commented Apr 12, 2017 at 19:56
Do you want to duplicate the same bit position in every integer? Or will the bit you want to duplicate vary? — sgrg
– sgrg, Commented Apr 12, 2017 at 20:05
Still too straightforward: part1 = x & -(1 << pos); part2 = x & ((1 << (pos+1))-1); return (part1 << 1) | part2;. Select two pieces of the integer overlapping at the duplicated bit, and paste those pieces together without overlapping. — user2357112
– user2357112, Commented Apr 12, 2017 at 20:07

Socowi · Accepted Answer · 2017-04-13 18:43:29Z

1

Implementation

The naive way already seems pretty efficient to me:

mask = -1 << (pos + 1)
(x << 1) & mask | x & ~mask

Benchmark

I ran the code as follows:

import numpy as np
import time

array = np.arange(2 ** 27, dtype=np.uint64)
pos = 5

t = time.process_time()
mask = np.uint64(-1 << (pos + 1))
array = (array << 1) & mask | array & ~mask
print(time.process_time() - t)

The bit duplication took 0.95 seconds (average of several runs). Due to memory issues, I used only 2²⁷ entries. But we can expect the time for 2³² entries to be 2^32-27 × 0.95 s = 2⁵ × 0.95 s = 32 × 0.96 s = 30.4 s.

edited Apr 13, 2017 at 18:43

answered Apr 13, 2017 at 18:37

Socowi

27.9k4 gold badges41 silver badges72 bronze badges

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

Collectives™ on Stack Overflow

Duplicate bits in a big numpy array

1 Answer 1

Implementation

Benchmark

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Implementation

Benchmark

Comments

Your Answer

Sign up or log in

Post as a guest

Related