Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bitwise Division

h14s.p5r.org

Post reply on HN
Print view View original

51–60 of 75 posts

Re: Bitwise Division

#51

Post by vanderZwan »

cornholio wrote: post #40
Matheus28 wrote: post #37

Earlier quoted context omitted.

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.

The method in the blog post uses two bit shifts and two additions. I don't really see how to beat that with this.

You can fit twenty-one 3-bit entries in a 64 bit int, with one bit to spare.

So naively you get:

   table[nlz / 21] >> (nlz % 21)
Which involves a division and a modulo. And that's assuming 63 entries in total, I'm not even trying to handle fitting the 64th entry in those three leftover bits somehow, or spread them across the three ints (again, I don't see how to do that without division).

Alternatively, each integer could contain one bit of the output, so:

   ((table[0] >> nlz) > nlz) > nlz)
Which is five shifts and two additions, so more work plus lookup.

If you see another method I overlooked please tell me.

Re: Bitwise Division

#52

Post by Aardwolf »

victor106 wrote: post #33

I always have a hard time grooking bit wise operations. Any good resources?

Think about all tricks you can so in decimal, but in base 2 instead.

E.g in decimal you can multiply by ten by appending a zero, so in binary you multiply by 2 by doing so. And left shifting by 1 is what appends a zero.

Or you can take approximate log base ten in decimal by counting amount of digits, so in binary you can approximate log2 this way (counting up to most significant one-bit). Etc...

Re: Bitwise Division

#53

Post by jsd1982 »

Very nice description of the bitwise maths, however I'm curious what lead to the need for `(63 - nlz) / 7` in the first place. A divisor of 7 is an odd thing to find when dealing with power-of-2-sized integers. Maybe this expression is used in some sort of expected length calculation to find the number of bytes which would be used for preallocating buffers? In most variable length encoder loops I've seen, you would just do a few bit twiddles to compute your encoded byte values and your exit condition should be a trivial check if there are remaining non-zero bits.

Re: Bitwise Division

#54

Post by cornstalks »

jsd1982 wrote: post #53

Very nice description of the bitwise maths, however I'm curious what lead to the need for `(63 - nlz) / 7` in the first place. A divisor of 7 is an odd thing to find when dealing with power-of-2-sized integers. Maybe this expression is used in some sort of expected length calculation to find the number of bytes which would be used for preallocating buffers? In most variable length encoder loops I've seen, you would j…

OP mentions "playing around with variable-length integer encodings."

`(63 - nlz) / 7` presumably tells you how many bytes you need to read for the varint. The length could be signaled by the number of leading zeros in the first byte (nlz), and each subsequent byte could set a high continuation bit (à la UTF-8 and protobuf varints), thus providing 7 bits of information per byte.

I'm totally speculating but this is generally what I'd expect from the expression `(63 - nlz) / 7` in the context of varints. Continuation bits and leading-zero-counters are redundant but this wouldn't be the first time I've seen something encode redundant information.

Re: Bitwise Division

#55

Post by earlyam »

victor106 wrote: post #33

I always have a hard time grooking bit wise operations. Any good resources?

Start counting in binary on your fingers until you're just about "binary native". Also, perform operations, and think about why they behave the way they do.

It sounds a little woo-woo but going from representing something on paper (or worse, a display) to doing it with my hands really changed it for me. Humans likely evolved intelligence because we stood up and used our hands to manipulate our environment, I suspect we more fully engage our brains in important ways by doing something with our hands when we can.

You might start appreciating the imperial system of measurement though. You've been warned.

Re: Bitwise Division

#56

Post by dahart »

jameshart wrote: post #48
dahart wrote: post #39

Earlier quoted context omitted.

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…

But that requires turning ‘multiplication by a constant’ into a bitwise trick in exactly the same way that this is doing for division by a constant (albeit without the fuzziness about rounding).

Why’s that?

Re: Bitwise Division

#57

Post by vintermann »

bonzini wrote: post #16
vintermann wrote: post #11

Earlier quoted context omitted.

The divisor is from 0 to 63. The dividend is a variable bit length integer, i.e. a bigint.

Absolutely not, he needs to compute (63 - x) / 7, where x is computed from a 64-bit integers. There are no bigints involved.

Well, there are variable length integers involved, since it's as part of a way of representing variable length integers. But it seems you're right that x is just a regular machine int in this context, as an implementation detail. I misunderstood.

Re: Bitwise Division

#58

Post by fweimer »

RagnarD wrote: post #5

Wouldn’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.

It's possible to use a lookup table (sort of) in a register. With x86-64-v2 and later, the code is larger, but potentially faster due to the shorter dependency chain:

int div7 (int x) { return 9 - __builtin_popcountll (0x4081020408102040ULL >> x); }

https://godbolt.org/z/Wj6P6jYGM

I think any monotonic function on 0 .. 63 can be written this way, so should be possible to fold in the outer 63 - nlz expression, too.

Re: Bitwise Division

#59

Post by gregschlom »

fweimer wrote: post #58
RagnarD wrote: post #5

Wouldn’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.

It's possible to use a lookup table (sort of) in a register. With x86-64-v2 and later, the code is larger, but potentially faster due to the shorter dependency chain: int div7 (int x) { return 9 - __builtin_popcountll (0x4081020408102040ULL >> x); } https://godbolt.org/z/Wj6P6jYGM I think any monotonic function on 0 .. 63 can be written this way, so should be possible to fold in the outer 63 - nlz expression, too.

This is a very cool technique. Someone ought to benchmark this vs the method described in the original article.

Re: Bitwise Division

#60

Post by grishka »

Waterluvian wrote: post #44

I learned about shifting to divide or multiply when writing my game boy emulator. Something I find fascinating is the lack of precision needed for games of that fidelity. Say you’re animating a jump and the character slows down towards the apex. I’ve seen an approach where it’s just “every X frames halve the speed until it’s zero.” This is done with the `SLA` (shift-left, LSB to 0) and `SRL` (shift-right, MSB to 0)`…

I also wrote a game boy emulator recently with the purpose of educating myself. I haven't looked that deep into what games do wrt math, but I was really impressed with all the creative ways they abuse the PPU by changing its various registers mid-frame. "Batman return of the Joker" for example uses this interesting effect of "compressing" the upper portion of the screen when you enter the options menu. It does this by changing the scroll Y to specific values on specific lines.

Though I do have some math-related problems in there. I spent several hours on it but I couldn't figure out how the SBC instruction should affect the carry flags. No matter what I do I can't pass the test ROMs.

But even with that, many of my childhood games are 100% playable. Writing a video game console emulator is a rewarding experience!

Post reply on HN