CODEWITHSUNDEEP
bit-manipulation
Tim C
Tim C

Reputation: 13

What transformation solves this bit-twiddling pattern?

I have a series of nibbles (0x0 - 0xF) and a resulting transformation for which a clear pattern results. The transformation solution simply isn't coming to me (not for a lack of trying). Is there an experienced bit twiddler out there that recognizes the transformation? Thanks in advance.

0 -> 0
1 -> 1
2 -> 1
3 -> 0
----------
4 -> 2
5 -> 3
6 -> 3
7 -> 2
----------
8 -> 7
9 -> 6
A -> 6
B -> 7
----------
C -> 5
D -> 4
E -> 4
F -> 5

Upvotes: 1

Views: 102

Answers (1)

Paul R
Paul R

Reputation: 212979

Looking at the individual bits it appears that one possible relationship between input and output would be:

Y0 = X0^X1^X3
Y1 = X2^X3
Y2 = X3
Y3 = 0

where X0..X3 are the input bits and Y0..Y3 are the output bits.

However this requires around 10 or more bitwise operations to implement, so you might be better off just using a lookup table.

Here is a test program in C which verifies that the bitwise logic is correct:

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

static int convert_bitwise(int x)
{
    int x0 = x & 1;
    int x1 = (x & 2) >> 1;
    int x2 = (x & 4) >> 2;
    int x3 = x >> 3;
    int y0 = x0 ^ x1 ^ x3;
    int y1 = x2 ^ x3;
    int y2 = x3;
    return (y2 << 2) | (y1 << 1) | y0;
}

static int convert_lut(int x)
{
    const int LUT[16] = { 0, 1, 1, 0,
                          2, 3, 3, 2,
                          7, 6, 6, 7,
                          5, 4, 4, 5 };
    return LUT[x & 0x0f];
}

int main(int argc, char *argv[])
{
    int x;

    for (x = 0; x < 16; ++x)
    {
        int y_bitwise = convert_bitwise(x);
        int y_lut = convert_lut(x);

        printf("x = %2d, y (bitwise) = %d, y (LUT) = %d, (%s)\n", x, y_bitwise, y_lut, y_bitwise == y_lut ? "PASS" : "FAIL");
    }
    return 0;
}

Test:

$ gcc -Wall bits4.c && ./a.out 
x =  0, y (bitwise) = 0, y (LUT) = 0, (PASS)
x =  1, y (bitwise) = 1, y (LUT) = 1, (PASS)
x =  2, y (bitwise) = 1, y (LUT) = 1, (PASS)
x =  3, y (bitwise) = 0, y (LUT) = 0, (PASS)
x =  4, y (bitwise) = 2, y (LUT) = 2, (PASS)
x =  5, y (bitwise) = 3, y (LUT) = 3, (PASS)
x =  6, y (bitwise) = 3, y (LUT) = 3, (PASS)
x =  7, y (bitwise) = 2, y (LUT) = 2, (PASS)
x =  8, y (bitwise) = 7, y (LUT) = 7, (PASS)
x =  9, y (bitwise) = 6, y (LUT) = 6, (PASS)
x = 10, y (bitwise) = 6, y (LUT) = 6, (PASS)
x = 11, y (bitwise) = 7, y (LUT) = 7, (PASS)
x = 12, y (bitwise) = 5, y (LUT) = 5, (PASS)
x = 13, y (bitwise) = 4, y (LUT) = 4, (PASS)
x = 14, y (bitwise) = 4, y (LUT) = 4, (PASS)
x = 15, y (bitwise) = 5, y (LUT) = 5, (PASS)
$

Upvotes: 3

Related Questions