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.

Comments:

2013-11-09 20:18:47 = KrzaQ
{
Wiem, że trochę się czepiam, ale w tej funkcji łamiesz tzw. "strict aliasing". Poprawniejszą metodą by było zastosowanie memcpy lub std::copy.
}
2013-11-15 05:27:19 = doctor
{
Jako iż jestem z natury leniwy oraz lubię korzystać ze standardowej biblioteki C++ zaproponowałbym użycie klasy bitset:

for(int i =0; i < 256; i++)
{
std::cout << std::hex << i << ": ";
std::cout << std::bitset<8>(i).to_string() << std::endl;
}
}
2013-11-15 22:40:21 = noname
{
Jeśli już w pętli, to przecież wystarczy & i >>

void to_bin(unsigned char c, char *out)
{
unsigned char mask = 0x80;
for (unsigned char i = 0; i < 8; ++i, mask >>= 1)
out[i] = (c & mask ? 0x31 : 0x30);
out[8] = '\0';
}
}
2013-11-16 04:11:34 = doctor
{
Pętla którą zastosowałem była tylko i wyłącznie żeby przedstawić wyniki takie same jak u Gynvael'a. Korzystając ze standardowej biblioteki C++ wystarczyłoby jak zresztą to tylko:

bitset<8> moja_zmienna_w_formie_bitowej(jakas_zmienna_zadeklarowana_wczesniej);

i to wystarczy.

Co do tej metody to nie spełnia ona na pewno jednego z wymagań mianowicie nie wygląda ona strasznie. Co do tego czy sama klasa bitset ze standardowej biblioteki korzysta z pętli wewnątrz czy nie, tego niestety nie wiem.
}
2013-12-07 00:33:56 = mdsrv
{
fajne :)
}
2014-01-04 21:37:06 = <script>alert(31337);</script>
{
alert(1);
}

Add a comment:

Nick:
URL (optional):
Math captcha: 7 ∗ 7 + 4 =