How to alternate 2 booleans using bitwise operators?

Question

Suppose I have two 4-bit values, ABCDand ABCD. How to alternate it, so it becomes AaBbCcDdusing bitwise operators? Example in pseudo-C:

nibble a = 0b1001;
nibble b = 0b1100;
char c = foo(a,b);
print_bits(c); 
// output: 0b11010010

Note: 4 bits is just for illustration, I want to do this with two 32-bit ints.

Answer 1

This is called a perfect random operation, and it has been discussed in detail in the Bible by Beat Bish, Henry Warren's “Hacker Enthusiasm , ” section 7-2 “Mixing the Beats”.

, x 32- a 16- b 16 :

   unsigned int x = (a << 16) | b;   /* put a and b in place */

C- :

x = (x & 0x0000FF00) << 8 | (x >> 8) & 0x0000FF00 | x & 0xFF0000FF;
x = (x & 0x00F000F0) << 4 | (x >> 4) & 0x00F000F0 | x & 0xF00FF00F;
x = (x & 0x0C0C0C0C) << 2 | (x >> 2) & 0x0C0C0C0C | x & 0xC3C3C3C3;
x = (x & 0x22222222) << 1 | (x >> 1) & 0x22222222 | x & 0x99999999;

, , ( ) :

unsigned int t;  /* an intermediate, temporary variable */
t = (x ^ (x >> 8)) & 0x0000FF00;  x = x ^ t ^ (t << 8);
t = (x ^ (x >> 4)) & 0x00F000F0;  x = x ^ t ^ (t << 4);
t = (x ^ (x >> 2)) & 0x0C0C0C0C;  x = x ^ t ^ (t << 2);
t = (x ^ (x >> 1)) & 0x22222222;  x = x ^ t ^ (t << 1);

, , 64- 32- . , . , , . - 64- , .

64

64 . . , . 4 , 32- , , , - , - .

unsigned long long int t;  /* an intermediate, temporary variable */
t = (x ^ (x >> 16)) & 0x00000000FFFF0000ull;  x = x ^ t ^ (t << 16);
t = (x ^ (x >> 8))  & 0x0000FF000000FF00ull;  x = x ^ t ^ (t << 8);
t = (x ^ (x >> 4))  & 0x00F000F000F000F0ull;  x = x ^ t ^ (t << 4);
t = (x ^ (x >> 2))  & 0x0C0C0C0C0C0C0C0Cull;  x = x ^ t ^ (t << 2);
t = (x ^ (x >> 1))  & 0x2222222222222222ull;  x = x ^ t ^ (t << 1);

Answer 2

" Twiddling Hacks" :  https://graphics.stanford.edu/~seander/bithacks.html#InterleaveTableObvious

 uint32_t x = /*...*/, y = /*...*/;
 uint64_t z = 0;

 for (int i = 0; i < sizeof(x) * CHAR_BIT; i++) // unroll for more speed...
 {
     z |= (x & 1U << i) << i | (y & 1U << i) << (i + 1);
 }

, .

Answer 3

, , , , .

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>


uint64_t interleave(uint32_t a, uint32_t b) {
    uint64_t result = 0;
    int i;
    for (i = 0; i < 31; i++) {
        result |= (a >> (31 - i)) & 1;
        result <<= 1;
        result |= (b >> (31 - i)) & 1;
        result <<= 1;
    }

    // Skip the last left shift.
    result |= (a >> (31 - i)) & 1;
    result <<= 1;
    result |= (b >> (31 - i)) & 1;
    return result;
}
void printBits(uint64_t a) {
    int i;
    for (i = 0; i < 64; i++)
        printf("%lu", (a >> (63 - i)) & 1);
    puts("");
}
int main(){
    uint32_t a = 0x9;
    uint32_t b = 0x6;
    uint64_t c = interleave(a,b);
    printBits(a);
    printBits(b);
    printBits(c);
}

Answer 4

:

#include <limits.h>

typedef unsigned int       half;
typedef unsigned long long full;

full mix_bits(half a,half b)
{
    full result = 0;
    for (int i=0; i<sizeof(half)*CHAR_BIT; i++)
        result |= (((a>>i)&1)<<(2*i+1))|(((b>>i)&1)<<(2*i+0));
    return result;
}

Answer 5

I used two tricks / operations used in this post. How do you set, clear and switch one bit? from setting a bit at particular indexand checking the bit at particular index.

The following code is only implemented using these two operations.

int a = 0b1001;
int b = 0b1100;
long int c=0;
int index;   //To specify index of c
int bit,i;

//Set bits in c from right to left.
for(i=32;i>=0;i--)
{
    index=2*i+1;   //We have to add the bit in c at this index

    //Check a

    bit=a&(1<<i);  //Checking whether the i-th bit is set in a
    if(bit)
      c|=1<<index; //Setting bit in c at index

    index--;

    //Check b

    bit=b&(1<<i);  //Checking whether the i-th bit is set in b
    if(bit)
      c|=1<<index; //Setting bit in c at index
}
printf("%ld",c);

Output: 210which equals0b11010010