7 ms·
8-bit number to binary string
- eru 11y agoNice little problem. Thanks for sharing!
- acqq 11y agoThe big constants used in the formula void to_bin(unsigned char c, char *out) { *(unsigned long long*)out = 3472328296227680304ULL + (((c * 9241421688590303745ULL) / 128) & 72340172838076673ULL); } are much more obvious when they remain in hex: 0x3030303030303030 -- the byte array of '0's encoded as ASCII 0x8040201008040201 -- the magic 0x101010101010101 -- only 0 or 1 to be added to the appropriate array element Therefore, more readable: void to_bin(unsigned char c, char *out) { /* endian dependent, works on x86 */ *(unsigned long long*)out = 0x3030303030303030ULL + (((c * 0x8040201008040201ULL) >> 7) & 0x0101010101010101ULL); } The function is of course endian dependent (I'd add a comment about that fact in it) and the explanation of the quoted function on the page starts at "If you shift the the constant by 7 bits to the right." The page is a result of an edit where the older function (that ends with + c / 128;) was explained first. Still, nice.
- deleted 11y ago[deleted]
- seiji 11y agoTowards the bottom of the article it says: the last thing I did was changing the constants to decimal - they look way more scary this way ;> because, you know, programming should be innately difficult and confusing so we can laugh at others who understand less than we do. Never underestimate how many times code (any code) posted online will be copy/pasted throughout the world everywhere from school projects to production systems.
- Confusion 11y agoThis code was already difficult and confusing and the author obviously pokes fun at his own code by decimalizing the constants. No need to accuse him of elitist or immoral behaviour.
- acqq 11y agoIt's a good and common practice to keep the constants in the sanest form and not obfuscate them, see the collections of such functions, like the already quoted http://aggregate.org/MAGIC/ http://aggregate.org/MAGIC/ or like https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html By keeping the decimal constants he diminishes the chance to be attributed.
- stavrianos 11y agoSure, sure, in most contexts code as communication medium is laudable. Here, the game is to make people accustomed to understanding go "the hell just happened?" when it works. I like it.
- _yy 11y agoYeah but that does not apply to jokes.
- acqq 11y agoYou mean the whole article is a joke just because the article ends with "the last thing I did was changing the constants to decimal - they look way more scary this way"? I see it as a presentation of an efficient specialized function, just like the other bit hacks are (some already linked, one more, a whole book, here: http://www.hackersdelight.org/ http://www.hackersdelight.org/ ). If it's is to impress the uninitiated, such are more probable to not know the hex codes too. For them is the decimal number the one less scary than the hex one. For others, converting back to hex is just a tiny annoyance, nothing more.
- 11y ago
- deleted 11y ago[deleted]
- EdSharkey 11y agoI wish I could do this in JavaScript.
- irascible 11y agoYou can but you have to use jquery.
- seiji 11y agoHere's a fancier, slightly less-magic, version. How to compile is left as an exercise for the reader (hint: Haswell or newer, requires BMI2 instruction set): void toBinary(uint8_t byte) { uint64_t zeroes = *(uint64_t *)"00000000"; uint64_t resultStr = zeroes | __builtin_bswap64(_pdep_u64(byte, 0x0101010101010101ULL)); printf("hello: %.*s\n", 8, (char *)&resultStr); }
- acz 11y agoThis really reminds me of the old demoscene diskmag Hugi article about adding 16 bit colors (without MMX). http://www.hugi.scene.org/online/hugi18/cobrad.htm http://www.hugi.scene.org/online/hugi18/cobrad.htm
- anewhnaccount2 11y agoThis is an example of SIMD Within A Register. There are some more neat examples here: http://aggregate.org/MAGIC/ http://aggregate.org/MAGIC/
- personjerry 11y agoAwesome. I'm always amazed by bitmagic like this. Today I saw one on stackoverflow and spent a good deal of time failing to understand it: https://stackoverflow.com/questions/33532045/how-to-swap-first-2-consecutive-different-bits https://stackoverflow.com/questions/33532045/how-to-swap-fir... And of course I'm reminded of the fast inverse square root: https://en.wikipedia.org/wiki/Fast_inverse_square_root https://en.wikipedia.org/wiki/Fast_inverse_square_root
- zamalek 11y ago> x86 is little endian - that's why it's backwards This can be read the wrong way, although it is correct: the author is referring to the final byte sequence and not the input bit sequence. Endianness applies to bytes, not bits.
- rjmunro 11y agoRather than add 0x3030303030303030, you could OR with it because you know there will never be a carry. This may save cycles on some architectures.
- rlonstein 11y agoCool but I want to say I've seen similar, google turns up: http://www.asmcommunity.net/forums/topic/?id=28498 http://www.asmcommunity.net/forums/topic/?id=28498
- nialo 11y agoWhy isn't this faster than the "standard" loop based version? The disclaimer at the start says it's not, but I would have thought that 4 64bit math operations would be much faster than a loop with 8 steps and comparisons and so on.
- acqq 11y agoIt is surely faster on modern 64-bit CPU's, and surely not faster on the 8-bit ones.
- cnvogel 11y agoFirst and foremost: YES, I KNOW! This is completely senseless microbenchmarking and micro-optimization. I ONLY LOOK AT THIS FOR FUN. That being said. The 64bit multiplication is faster, and also constant in time. I've measured this using the timestamp counter which doesn't necessarily count actual CPU clock cycles, but possibly an integer multiple of it (seems to output always numbers divisable by 8 for me). (...) 100 loop:01100100(152) 64bit:01100100(48) 101 loop:01100101(128) 64bit:01100101(48) 102 loop:01100110(160) 64bit:01100110(48) 103 loop:01100111(128) 64bit:01100111(48) 104 loop:01101000(192) 64bit:01101000(48) 105 loop:01101001(88) 64bit:01101001(48) 106 loop:01101010(152) 64bit:01101010(48) 107 loop:01101011(128) 64bit:01101011(48) 108 loop:01101100(160) 64bit:01101100(48) (...) That's on an Intel(R) Core(TM) i5 CPU M 450 @ 2.40GHz and the cycles include the rdtsc, a few movs, and the call to the respective function. https://github.com/vogelchr/bitstring_via_64bit_mult https://github.com/vogelchr/bitstring_via_64bit_mult
- acqq 11y agoThanks for measuring. From your github source: /* anyone have a big-endian machine at hand to test this? */ #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ #define MULT 0x8040201008040201ULL #else #define MULT 0x0102040810204080ULL #endif Even without the machine I believe that such a big endian implementation can't work. Hint: you can try it on the little endian machine too, the resulting bits must be appropriate, and I believe they wouldn't. That's the beauty of the magic constants, their construction isn't so easy as it appears to be.
- amelius 11y agoFeature request: add a parameter that specifies the base into which the function rewrites the number.
- est 11y agoFor Python >>> f1=lambda c: __import__('struct').pack('<Q', 3472328296227680304 + (((c * 9241421688590303745) / 128) & 72340172838076673)) >>> f1(1) '00000001' >>> f1(2) '00000010' >>> f1(5) '00000101' >>> f2=lambda c: struct.pack('<Q', (((c * 0x8040201008040201) / 128) & 0x0101010101010101)) >>> f2(1) '\x00\x00\x00\x00\x00\x00\x00\x01' >>> f2(2) '\x00\x00\x00\x00\x00\x00\x01\x00' >>> f2(101) '\x00\x01\x01\x00\x00\x01\x00\x01' Use "<" for little-endian for x86
- nwmcsween 11y agoI recommend reading over this: http://0x80.pl/articles/convert-to-bin.html http://0x80.pl/articles/convert-to-bin.html btw all this SWAR stuff should be aligned before applying.
- jjnoakes 11y agoBe careful with alignment. On architectures where it matters, the caller may pass in a "char* out" which is not suitably aligned, and doing an "unsigned long long" store into that address may fault.