Wczoraj wieczorem, zainspirowany pewną dyskusją na IRCu, spróbowałem zrobić funkcję do konwersji 8-bitowej liczby (unsigned char) na string będący reprezentacją bitową tej liczby (i.e. 0xF3 → "11110011"). Oczywiście to bardzo prosta sprawa - w zasadzie jest to jedno z podstawowych ćwiczeń, z którymi sobie radzą nawet bardzo początkujący programiści. Więc... czemu by sobie nie utrudnić zabawy? Dorzuciłem więc założenia: nie może być pętli (nawet rozwiniętej), musi wyglądać matematycznie, oraz w miarę strasznie/nieczytelnie (funkcja pisana w okolicy halloween ;>). I nawet się udało.

TL;DR, czyli kod:
void to_bin(unsigned char c, char *out) {
 *(unsigned long long*)out = 3472328296227680304ULL +
   (((c * 9241421688590303745ULL) / 128) & 72340172838076673ULL);
}(Disclaimer: metoda nie jest najszybsza, nie jest najlepsza, delikatnie nagina standard (implementation defined) i nie jest to kod produkcyjny; metoda po prostu jest i fajnie się nad nią myślało ;>)

Założenia były następujące:
• Wynikiem musi być zawsze 8 cyfr.
• NUL-byte ('\0') jest dodawany w innym miejscu.
• Ma działać na x86.

I tak, powyższa metoda działa:
#include <stdio.h>

void to_bin(unsigned char c, char *out) {
 *(unsigned long long*)out = 3472328296227680304ULL +
   (((c * 9241421688590303745ULL) / 128) & 72340172838076673ULL);
}

int main(void) {
 int i;

 char buf[256] = {0};
 for(i = 0; i < 256; i++) {
   to_bin(i, buf);
   printf("%.2x: %s\n", i, buf);
 }

 return 0;
}

Output:
00: 00000000
01: 00000001
02: 00000010
03: 00000011
04: 00000100
...
5d: 01011101
5e: 01011110
5f: 01011111
60: 01100000
...
fd: 11111101
fe: 11111110
ff: 11111111
Jeśli chodzi o wyjaśnienie jak to działa - po pierwsze, zachęcam do spróbowania zrobienia samemu podobnej funkcji o takich założeniach. Po drugie, próba zrewersowania tej funkcji może być ciekawym doświadczeniem (warto prześledzić przepływ bitów - dużo lepiej będzie widać co się dzieje).
Natomiast dla zainteresowanych przygotowałem mały write-up (w języku angielskim):
8-bit number to binary string ("01011010") [C/C++]

Oczywiście mając już powyższe stałe (szczególnie tą przy mnożeniu) można je wrzucić w google, i wtedy okazuje się, że już kilka osób wpadło na podobne rozwiązania (as to be expected ;>).

Wpadając w dygresję: z benchmarków robionych przez autora tej metody (która jest bardzo zbliżona do prezentowanej przeze mnie powyżej) wynika, że ta metoda jest szybsza od tradycyjnej pętli (na x86-64, niekoniecznie na x86-32), oraz, że metoda z LUT jest jeszcze szybsza. O ile jestem w stanie uwierzyć w to pierwsze, to LUT będzie szybsze jedynie przy częstym, wielokrotnym użyciu - ponieważ wtedy cała tablica będzie w cache. W przeciwnym wypadku, dla pojedynczych wywołań, mam wrażenie, że metoda z LUT będzie zdecydowanie najwolniejsza.

I tyle.