(63 - nlz) / 7, where nlz is between 0 and 63 lookup table with 64 entries anyone?
A bitshift oneliner IS nicer.
Maybe nicer, but slower. And I'm not even sure about the former.
Bitwise Division
31–40 of 75 posts
Re: Bitwise Division
#32ChatGPT tells me: Dividing a number by 7 using bitwise operations can be done using a technique called "magic numbers." This involves precomputing a number that, when combined with bitwise operations, will give the correct result. Here's how it can be done: First, we need to find a "magic number" that will help us divide by 7. One way to do this is to use the fact that 7 is a prime number, which means that there is a…
so... 7/7 = (7+(7>>3))*3 = 21? gotcha
Re: Bitwise Division
#33I always have a hard time grooking bit wise operations. Any good resources?
Re: Bitwise Division
#34I always have a hard time grooking bit wise operations. Any good resources?
I think wikipedia does a quite good job explaining what different operations do: https://en.m.wikipedia.org/wiki/Bitwise_operation
Re: Bitwise Division
#35Wouldn’t a lookup table be a whole lot easier? I’d think a 64 entry table of integers would be fast to access once cached.
I don't use lookup tables that much when optimizing these days, because most math instructions cost far fewer cycles than a cache miss. And even if your lookup table is in L3, it still costs ~40 cycles to retrieve each line.
That's a good instinct to have. However in this case the input is 0..63 and the output comfortably sits in a single byte. It can fit in just one cache line if you bother to align it.
The miss cost is, therefore, not really relevant: if this code is hotpath at all the cost of a single cache miss is amortized across millions of calls. Your lookup table will be in cache as surely as the code that reads it is.
Re: Bitwise Division
#36I always have a hard time grooking bit wise operations. Any good resources?
Honestly just practice. They cost me an interview I really wanted once, so now anytime I stumble across one in a project I take extra time to read and understand it. I also make a point of using bitmasks as function arguments in places where that's a good/reasonable choice.
Re: Bitwise Division
#37Re: Bitwise Division
#38(63 - nlz) / 7, where nlz is between 0 and 63 lookup table with 64 entries anyone?
It might be slower to use a memory access, even if you assume an average L1 cache hit. You can pipeline the bitwise version and maybe achieve an amortized divide in one cycle, where (depending on process and many other things) the lookup table might peak at like 4 cycles per divide even in unrolled/parallel situations. Plus the technique in the article is good for just about any constant divisor and if generalized works on much larger ranges, it’s why many compilers use this trick when they can.
Re: Bitwise Division
#39Nice, if a little bit hand wavy. Seems a little bit of a stretch to call an operation that still includes a multiply bitwise , though.
Naw, it’s standard to call such tricks “bitwise” even when including a multiply. Remember you’re multiplying into a specific bit range and then shifting down (dividing by a power of 2) to capture the bits you want, it’s bitwise in a very literal sense. Probably quite fair to call any expression “bitwise” if any single operation in the expression is bitwise, regardless of the other operators & functions, no? What part is hand-wavy? Variations of this technique are in standard widespread usage in the compilers we use.
Re: Bitwise Division
#40Earlier quoted context omitted.
Maybe nicer, but slower. And I'm not even sure about the former.
Probably faster: no memory loads, no cache pressure
Cache pressure is not really relevant, the result can be represented in 3 bits, so the entire table can fit in three 64 bit ints. It's uglier and you still need to do bitshifts, but much easier to write.