/* yet more bit hacks */

#include <stdio.h>

typedef int bool;
#define true 1
#define false 0

#define CHAR_BIT 8

int main(void) {

/* 1) count parity */

unsigned int v = 847362849;
bool parity = false;

while (v)
{
  parity = !parity;
  v = v & (v - 1);
}

printf("%d\n", parity);

static const bool ParityTable256[256] =
{
#   define P2(n) n, n^1, n^1, n
#   define P4(n) P2(n), P2(n^1), P2(n^1), P2(n)
#   define P6(n) P4(n), P4(n^1), P4(n^1), P4(n)
    P6(0), P6(1), P6(1), P6(0)
};

v = 847362849;
v ^= v >> 16;
v ^= v >> 8;
parity = ParityTable256[v & 0xff];
printf("%d\n", parity);

v = 847362849;
unsigned char * p = (unsigned char *) &v;
parity = ParityTable256[p[0] ^ p[1] ^ p[2] ^ p[3]];
printf("%d\n", parity);

unsigned char b = 73; // byte value to compute the parity of
parity =
  (((b * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1;
printf("%d\n", parity);

printf("\n");

/* 2) reversing bits */

v = 847362849; // input bits to be reversed
unsigned int r = v; // r will be reversed bits of v; first get LSB of v
int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end

for (v >>= 1; v; v >>= 1)
{
  r <<= 1;
  r |= v & 1;
  s--;
}
r <<= s; // shift when v's highest bits are zero

printf("%d\n", r);

static const unsigned char BitReverseTable256[256] =
{
#   define R2(n)     n,     n + 2*64,     n + 1*64,     n + 3*64
#   define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
#   define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )
    R6(0), R6(2), R6(1), R6(3)
};

v = 847362849; // reverse 32-bit value, 8 bits at time
unsigned int c; // c will get v reversed

c = (BitReverseTable256[v & 0xff] << 24) | 
    (BitReverseTable256[(v >> 8) & 0xff] << 16) | 
    (BitReverseTable256[(v >> 16) & 0xff] << 8) |
    (BitReverseTable256[(v >> 24) & 0xff]);

printf("%d\n", c);

p = (unsigned char *) &v;
unsigned char * q = (unsigned char *) &c;
q[3] = BitReverseTable256[p[0]];
q[2] = BitReverseTable256[p[1]];
q[1] = BitReverseTable256[p[2]];
q[0] = BitReverseTable256[p[3]];

printf("%d\n", c);

b = 73; // reverse this (8-bit) byte

b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;

printf("%d\n", b);

printf("\n");

/* 3) integer logarithm base-2 */

v = 847362849; // 32-bit word to find the log base 2 of
r = 0; // r will be lg(v)

while (v >>= 1)
{
  r++;
}

printf("%d\n", r);

static const char LogTable256[256] =
{
#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
    -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
    LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
    LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
};

v = 847362849; // 32-bit word to find the log of
register unsigned int t, tt; // temporaries

if (tt = v >> 16)
{
  r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
}
else
{
  r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}

printf("%d\n", r);

if (tt = v >> 24)
{
  r = 24 + LogTable256[tt];
}
else if (tt = v >> 16)
{
  r = 16 + LogTable256[tt];
}
else if (tt = v >> 8)
{
  r = 8 + LogTable256[tt];
}
else
{
  r = LogTable256[v];
}

printf("%d\n", r);

return 0; }

1
1
1
1

-2065858228
-2065858228
-2065858228
146

29
29
29