(untitled)

Recently I rediscovered pic related and I got to thinking about bitwise operations/tricks/hacks. So I wanted to make a thread about it. Most programmers probably learn them pretty early on and use them probably pretty rarely. I know some of you will find everything here completely trivial but if you're new to programming or you just find this stuff cool and interesting, stick around and post your best/coolest/most useful bitwise tricks. I'm gonna start with some basic stuff. The basic operations are: operation: symbol (commonly) and : & or : | not : ~ xor : ^ There are others like nor but afaik those don't commonly have their own symbols but are rather constructed from these basic ones (nor would be ~(x | y) where x and y are the two input bits). Also there is the bitshift operations. Let's just say the << and >> operations are logical shifts ( https://en.wikipedia.org/wiki/Bitwise_operation#Boolean_algebra ) unless otherwise specified. Alright now that we're on the same page about the symbols, we can get started. If you don't know how something works I encourage you to figure it out on pen and paper, some of these are very simple. Some cool tricks I use from time to time: >x*2^n x << n >Biggest number you can represent with x bits (1 << x) - 1 >Dividing x by 2 x >> 1 Shifting 1 to the right by the number you want to divide gives you x/2 given that x is divisble by 2 (if not it rounds down to nearest integer). >Set nth bit of a sequence of bits x to 1 x = (1 << n) | x For example if x = 0b1000 and n =2, then: (1 << n) = 0b0100 0b1000 ^ 0b0100 = 0b1100 >Set nth bit of a sequence of bits x to 0 x = ~(1 << n) & x >Toggle nth bit of a sequence of bits x x = (1 << n) ^ x >Is x a power of two? (x & (x - 1)) == 0 This will return true if x is a power of two, false otherwise. >Kernighan's population count count = 0 while (c != 0): x = x & (x - 1) count++ This one counts how many 1s are in x. >Changing the sign of sequence x -x = ~x + 1 >swap x and y x = x ^ y y = x ^ y x = x ^ y No temp variable needed! >Pic related for i in range(4): B ^= A C ^= B A ^= C B ^= A C ^= B Here by "^= " I mean for example B^=A <=> B = B^A. Also this is not really a bit hack/manipulation but still useful and kinda related: If you have a system with n states, you need x=log2(n) number of bits to represent that system's state (round up to integers). This is kinda obvious if you think about it: 2^x is the number of possible states you can express with x bits. For example, a system with 4 possible states can be expressed with 2 bits (00, 01, 10, 11) and this works for any number of bits.

>>30870 Oops I made a mistake. Kernighan's population count goes like this: count = 0 while (x != 0): x = x & (x - 1) count++

Fairly simple one: >Is x odd? x & 1

>>30873 Nice, simple but useful

Protip: let the compiler do its work when your n is a compile time constant, it'll be more readable.

>>30883 For sure, some of these I just run quickly on a python interpreter for whatever reason. For actual bit level manipulation these are readable I think but it's not often one has to do that really.

Can someone tell me how to use a Karnaugh map?

>>30885 Do you have a specific question? If you want to just generally learn how to use them here's a great video: https://www.youtube.com/watch?v=RO5alU6PpSU

>>30873 Opaque. Use is_even.js instead.

>>30897 >.js 1/10 bait, can do better.

you can use bitwise operation on a switch statement. it's pretty cool, i like it.

>>31092 What are you talking about? This is just doing bitwise operations on the value passed to switch, nothing specific to switch. What you probably mean is the technique of switching on multiple integers by merging their bits. By the way, if you want your switches to be as fast as actual FORTRAN jump tables or non standard computed gotos, add a `default: __builtin_unreachable();` case.

>>30870 Recently stumbled across this which is a useful collection of trickery with bitwise logic: https://graphics.stanford.edu/~seander/bithacks.html

Xor is also useful for speedy and reliable PRNGs. https://en.m.wikipedia.org/wiki/Xorshift

first time posting on this site and i love that there is a thread like this OP i highly recommend checking out Hacker's Delight. It's full of hacks and tricks like this that may be of interest to you https://www.amazon.com/Hackers-Delight-2nd-Henry-Warren/dp/0321842685 You also might love AVX512's vpternlog{d,q} instruction: http://0x80.pl/articles/avx512-ternary-functions.html and maybe some stuff involving NPN classification https://people.eecs.berkeley.edu/~alanmi/publications/2013/icfpt13_npn.pdf

however file permissions works on POSIX is also bit magic.

>>31175 kind of a weird unintuitive design but it did force me to learn bit arithmetic and masking a bit. I'm sure people dealing with subnet masks and such got filtered by it similarly.

The funny thing about the 'xor trick' is that it is generally slower than using three MOV statements on most processors because it has to touch the ALU. >>30883 Usually. If you're writing a super-hot inner loop or something that needs to have absolutely minimum latency, and you need to optimize the fuarrrk out of it there's really no way to know for sure without reading the assembly.

>>32548 Isn't this trick obsolete by the xchg instruction? This would be faster too though as it's just a register-rename operation within the hardware's register-file.

>>30870 I found this goldmine out of curiosity: https://graphics.stanford.edu/~seander/bithacks.html computer parity of a byte: unsigned char b; // byte value to compute the parity of bool parity = (((b * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1;

>>36729 almost a year-old bump man. Cool trick. I believe this is just a parallel prefix xor of some kind. You can generalize the same thing using a carryless-multiplication. I believe ARM CPUs support this natively as well through their polynomial types https://wunkolo.github.io/post/2020/05/pclmulqdq-tricks/

>>36737 Old threads are worth bumping man

>>36738 I agree. I'd much rather see better old threads hang on longer than get much more quickly replaced by worse threads just because they're newer. The hyper-engaged, instant-gratification mindset of the new web always ends up like kicking dead whales down the beach anyway. I've seen so many great or informative threads here over the years, including this one, that I'd replace at least a third of the catalogue's current threads. The problem with the format is that complicated threads are harder to contribute to than simpler threads, so are at an evolutionary disadvantage unless you relax the technically correct but dubious at higher orders demand that bumps maintain the relative quality and newness of the thread. Worse threads are lesser in absolute quality, so the same type of bumps applied to better threads are better in the context of the whole board, as they compensate for the disadvantage better threads are at under the narrow definition of good contribution. Do your part and keep great threads active, lainons. Or don't, if it's all water under the bridge anyway. Present Day, present Time.

>>36729 Calculating modulo on a 64 bit integer is pretty expensive, so I did a quick & rough benchmark to see if it's actually faster. int parity_naive(unsigned char b) { int x = 0; for (int i = 0; i < 8; i++) { x ^= (b >> i) & 1; } return x; } int parity_divide_and_conquer(unsigned char b) { b = (b & 15) ^ (b >> 4); b = (b & 3) ^ (b >> 2); b = (b & 1) ^ (b >> 1); return b; } int parity_stanford(unsigned char b) { return (((b * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1; } int main() { volatile int x; for (int k = 0; k < 1000000; k++) { for (volatile int i = 0; i < 255; i++) { #if NAIVE x = parity_naive(i); #elif DIVIDE_AND_CONQUER x = parity_divide_and_conquer(i); #elif STANFORD x = parity_stanford(i); #else #endif } } } real0m0.070s user0m0.070s sys0m0.000s lain@pc:/tmp$ gcc -O3 -DNAIVE x.c && time ./a.out real0m0.273s user0m0.273s sys0m0.000s lain@pc:/tmp$ gcc -O3 -DDIVIDE_AND_CONQUER x.c && time ./a.out real0m0.185s user0m0.184s sys0m0.000s lain@pc:/tmp$ gcc -O3 -DSTANFORD x.c && time ./a.out real0m0.224s user0m0.224s sys0m0.000s Looking at the assembly: 0000000000000000 <parity_naive>: 0: 40 0f b6 c7 movzx eax,dil 4: 89 c2 mov edx,eax 6: 89 c1 mov ecx,eax 8: c1 f9 02 sar ecx,0x2 b: d1 fa sar edx,1 d: 31 ca xor edx,ecx f: 89 c1 mov ecx,eax 11: 31 d7 xor edi,edx 13: c1 f9 03 sar ecx,0x3 16: 89 c2 mov edx,eax 18: 31 f9 xor ecx,edi 1a: c1 fa 04 sar edx,0x4 1d: 31 ca xor edx,ecx 1f: 89 c1 mov ecx,eax 21: c1 f9 05 sar ecx,0x5 24: 31 d1 xor ecx,edx 26: 89 c2 mov edx,eax 28: c1 f8 07 sar eax,0x7 2b: c1 fa 06 sar edx,0x6 2e: 31 ca xor edx,ecx 30: 83 e2 01 and edx,0x1 33: 31 d0 xor eax,edx 35: c3 ret 36: 66 2e 0f 1f 84 00 00 cs nop WORD PTR [rax+rax*1+0x0] 3d: 00 00 00 0000000000000040 <parity_divide_and_conquer>: 40: 89 f8 mov eax,edi 42: 40 c0 ef 04 shr dil,0x4 46: 83 e0 0f and eax,0xf 49: 31 c7 xor edi,eax 4b: 89 f8 mov eax,edi 4d: 83 e7 03 and edi,0x3 50: c0 e8 02 shr al,0x2 53: 31 f8 xor eax,edi 55: 89 c2 mov edx,eax 57: d0 ea shr dl,1 59: 31 d0 xor eax,edx 5b: 83 e0 01 and eax,0x1 5e: c3 ret 5f: 90 nop 0000000000000060 <parity_stanford>: 60: 48 b8 01 01 01 01 01 movabs rax,0x101010101010101 67: 01 01 01 6a: 40 0f b6 ff movzx edi,dil 6e: 48 0f af f8 imul rdi,rax 72: 48 b8 01 02 04 08 10 movabs rax,0x8040201008040201 79: 20 40 80 7c: 48 21 c7 and rdi,rax 7f: 48 b8 03 04 08 10 20 movabs rax,0x80402010080403 86: 40 80 00 89: 48 f7 e7 mul rdi 8c: 48 89 f8 mov rax,rdi 8f: 48 29 d0 sub rax,rdx 92: 48 d1 e8 shr rax,1 95: 48 01 c2 add rdx,rax 98: 48 c1 ea 08 shr rdx,0x8 9c: 8d 04 17 lea eax,[rdi+rdx*1] 9f: 83 e0 01 and eax,0x1 a2: c3 ret There's no actual modulus operation, which I expected, though it is apparently still slower.

One trick I find myself using fairly often is to quickly compute a power-of-two mask by rounding up an integer to the nearest power-of-two. x |= x >> 1 x |= x >> 2 x |= x >> 4 x |= x >> 8 x |= x >> 16 ... This sequence duplicates the top bit to the bit immediately below, then the top 2 bits to the 2 bits immediately below, then the top 4 bits ... At the end the top set bit has been duplicated to all the lower bits. Useful if you have a collection and you want to avoid expensive modulus operations (e.g. hashmap).

Technically not a bit hack but regardless something I believe every programmer should know. Calculating divisions is slow while multiplications are fast on modern hardware, so it's useful to first calculate the reciprocal (i.e. 1/x), then multiply with it. Of course we can't do that directly with integers. But we can make use of a fixed-point format. Calculate in fixed point, then convert back to integers. For example, let's say we want to divide a positive 32 bit integer by 5. We make use of fixed point numbers with a 32 bit integer part and 32 bit fractional part. 1/5 in fixed-point format is (+1 to account for shift right rounding down): 1/y = ((1 << 32) / y) + 1 ==> 1/5 = ((1 << 32) / 5) + 1 = 858993460 [code] To multiply with 1/5: [code] x / y = x * 1/y = (x * 858993460) >> 32 Let's try it! x = 42 (x * 858993460) >> 32 = 8 x = 1337 (x * 858993460) >> 32 = 267 x = 123456789 (x * 858993460) >> 32 = 24691357

>>37817 for finding parity, you can do a singular carry-less multiplication too, up to 64-bits https://wunkolo.github.io/post/2020/05/pclmulqdq-tricks/ The "Prefix Xor" section implies that you could just pclmulqdq with 1111111.... and then check a singular bit in the result to get the parity.

>>38168 While a neat trick, at least on a 5800X it isn't any faster for 64 bit parity, and much slower for 8 bit. For 64 bit parity it is much shorter though, so better on icache. int parity_clmul(unsigned char b) { __m128i x = _mm_set_epi64x(0, b); __m128i y = _mm_set1_epi8(0xff); __m128i z = _mm_clmulepi64_si128(x, y, 0); return (_mm_cvtsi128_si64(z) >> 7) & 1; } 0000000000001280 <parity_clmul>: 1280:40 0f b6 ff movzx edi,dil 1284:c5 f1 76 c9 vpcmpeqd xmm1,xmm1,xmm1 1288:c4 e1 f9 6e c7 vmovq xmm0,rdi 128d:c4 e3 79 44 c1 00 vpclmullqlqdq xmm0,xmm0,xmm1 1293:c4 e1 f9 7e c0 vmovq rax,xmm0 1298:48 c1 f8 07 sar rax,0x7 129c:83 e0 01 and eax,0x1 129f:c3 ret $ cc -O3 parity.c -march=native -DCLMUL && time ./a.out real0m0.424s user0m0.424s sys0m0.000s FWIW, while looking up whether there were clmul instructions for lower bitsizes (32, 16, 8) I found a comment mentioning the use of a lookup table for 4-bit parity. Applying it to the D&C algorithm made it a bit faster. int parity_divide_and_conquer_lut(unsigned char b) { b = (b & 15) ^ (b >> 4); return (0x6996U >> b) & 1; 00000000000011f0 <parity_divide_and_conquer_lut>: 11f0:89 f9 mov ecx,edi 11f2:83 e7 0f and edi,0xf 11f5:b8 96 69 00 00 mov eax,0x6996 11fa:c0 e9 04 shr cl,0x4 11fd:31 f9 xor ecx,edi 11ff:d3 e8 shr eax,cl 1201:83 e0 01 and eax,0x1 1204:c3 ret $ cc -O3 parity.c -DDIVIDE_AND_CONQUER_LUT && time ./a.out real0m0.140s user0m0.140s sys0m0.000s

>>38171 Alright you nerd-sniped me. I'm the guy that wrote the article and now this is piquing my interest >5800X You support GFNI instructions. I wrote a couple posts about this: https://wunkolo.github.io/post/2020/11/gf2p8affineqb-bit-reversal/ https://wunkolo.github.io/post/2020/11/gf2p8affineqb-int8-shifting/ A byte-parity calculation could just be: uint8_t ByteParity(uint8_t Byte) { const __m128i Parity = _mm_gf2p8affine_epi64_epi8( _mm_set1_epi8(Byte), _mm_set1_epi64x( // Bit 0 is the XOR of all bits in the byte // V 0b11111111'00000000'00000000'00000000'00000000'00000000'00000000'00000000 ), 0x0 ); return static_cast<uint8_t>(_mm_cvtsi128_si32(Parity)); } ByteParity(unsigned char): vpbroadcastb xmm0, edi vgf2p8affineqb xmm0, xmm0, XMMWORD PTR .LC0[rip], 0 vmovd eax, xmm0 ret This might be slow due to some XMM register movement, but you could do up to 16(SSE), 32(AVX), or 64(AVX512)-bytes of byte-parities at the same time if you wanted to.

I was bored and wondered about the (likely) fastest algorithm for getting the sign of a float32 I came up with this: float mysign(float x) { unsigned int y = *(unsigned int *)&x; if ((y & 0x7fffffff) != 0) y |= 0x3f800000; y &= 0xbf800000; return *(float *)&y; } Which compiles down to (gcc -O3): mysign: 50:66 0f 7e c0 movd eax,xmm0 54:89 c2 mov edx,eax 56:81 ca 00 00 80 3f or edx,0x3f800000 5c:a9 ff ff ff 7f test eax,0x7fffffff 61:0f 45 c2 cmovne eax,edx 64:25 00 00 80 bf and eax,0xbf800000 69:66 0f 6e c0 movd xmm0,eax 6d:c3 ret It checks if the number is 0 (exponent and mantissa both 0). If not, it sets the exponent to 0 (= 127-127). It also sets the mantissa to 0. With exponent >0 the value is 1, with exponent =0 the value is 0. The sign is preserved, so you get -1.0, 1.0, -0.0 or 0.0. I haven't tested it extensively, but it should work for all non-NaN numbers.

>>31171 >linking to amazon Absolutely jewish https://libgen.is/book/index.php?md5=34DCB990FEBE54887C83E5F9534F1957