Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Interleave bits efficiently

I need to make uint64_t out of 2 uint32_t interleaving the bits: if A=a0a1a2...a31 and B=b0b1...b31, I need C=a0b0a1b1...a31b31. Is there a way to do this efficiently? So far I've got only the naive approach with a for loop of 32 iterations, where each iteration does C|=((A&(1<<i))<<i)|((B&(1<<i))<<(i+1)).

I guess there should be some mathematical trick like multiplying A and B by some special number which results in interleaving their bits with zeros in the resulting 64-bit number, so that what only remains is to or these products. But I can't find such multiplier.

Another potential way to go is a compiler intrinsic or assembly instruction, but I don't know of such.

like image 298
Serge Rogatch Avatar asked Sep 14 '16 12:09

Serge Rogatch


People also ask

What is meant by bit interleaving?

Interleaving (bitmaps), a technique for encoding bitmapped images. Interleaving the bits of the binary representation of coordinate values to produce a Z-order (curve) for points. Interleave sequence, a mathematical sequence formed by interleaving members of two other sequences in alternation.

How do you make all bits 1?

Setting all bits can be done by using the | (OR) bit operator with 1s for each of the bits. This is because 1 OR with any number sets the number as 1.

How do you know if two bits are set?

Bitwise AND Operator (&) is used to check whether a bit is SET (HIGH) or not SET (LOW) in C and C++ programming language. Bitwise AND Operator (&) is a binary operator, which operates on two operands and checks the bits, it returns 1, if both bits are SET (HIGH) else returns 0.


2 Answers

NathanOliver's link offers the 16-bit -> 32-bit implementation:

static const unsigned int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF};
static const unsigned int S[] = {1, 2, 4, 8};

unsigned int x; // Interleave lower 16 bits of x and y, so the bits of x
unsigned int y; // are in the even positions and bits from y in the odd;
unsigned int z; // z gets the resulting 32-bit Morton Number.  
                // x and y must initially be less than 65536.

x = (x | (x << S[3])) & B[3];
x = (x | (x << S[2])) & B[2];
x = (x | (x << S[1])) & B[1];
x = (x | (x << S[0])) & B[0];

y = [the same thing on y]

z = x | (y << 1);

Which works by:

  1. leave the low 8 bits of x where they are. Move the high 8 bits up by 8;
  2. divide in half and do the same thing, this time leaving the low pairs of 4 bits where they are and moving the others up by 4;
  3. and again, and again.

I.e. it proceeds as:

   0000 0000 0000 0000  abcd efgh ijkl mnop
-> 0000 0000 abcd efgh  0000 0000 ijkl mnop
-> 0000 abcd 0000 efgh  0000 ijkl 0000 mnop
-> 00ab 00cd 00ef 00gh  00ij 00kl 00mn 00op
-> 0a0b 0c0d 0e0f 0g0h  0i0j 0k0l 0m0n 0o0p

And then combines the two inputs together.

As per my earlier comment, to extend that to 64 bits, just add an initial shift by 16 and mask by 0x0000ffff0000ffff, either because you can intuitively follow the pattern or as a divide-and-conquer step, turning the 32-bit problem into two non-overlapping 16-bit problems and then using the 16-bit solution.

like image 170
Tommy Avatar answered Oct 10 '22 04:10

Tommy


For larger integers, it's worth mentioning the clmul x86 extension for finite field multiplication (carryless multiplication). Interleaving an integer with zeros is equivalent to a carryless multiplication of the integer with itself, which is a single ALU instruction.

like image 25
saolof Avatar answered Oct 10 '22 03:10

saolof