next »

[Quarry]

Let's say I have a 5 bit number like 10010

I shift it by 2 to the right and OR it onto a byte so it become 00000100

How can I know the amount of bits that were "relevant" on the byte which is 3 in this case

I also need a solution that works when I shift it to the left! How can I go on about this?

[Columbo]

It's possible I've misunderstood the question, but I think the magic phrases to google are "Count leading zeros", "Count trailing zeros", "Find Most Significant Bit".

The solution you choose will depend on the hardware you're targeting and how much you enjoy the amazing bit twiddling hacks that are around. I love this page http://graphics.stanford.edu/~seander/bithacks.html, but it's usually pretty hard to justify using the tricks because of the readability cost from being too clever by half.

[Gregg Williams]

I guess the worse case scenario is 31 mask tests for a 32bit number, I'm sure there are cleverer ways though.

[ThemsAllTook]

http://graphics.stanford.edu/~seander/bithacks.html

+1 for this. Really great resource. For the "too clever by half" concern, I usually reference the URL in a comment next to the function I use from the page, just in case I come back later and can't remember what's going on.

[muki]

I find it really interesting that bitshifts and bit hacks in general are still used for game dev, even now that we have "unlimited processing power"!

I come from an embedded background. The only programming I did was for microcontrollers where bit manipulation was commonplace because we had to.  I haven't really done any game programming yet (except for some gamemaker) but it's nice to see it hasn't died!

[tbkn]

Logarithm will be your answer.
Do a logarithm to the byte, add 1, and then round it down to the nearest int.

So, if you have 5 (101), then log2(5) will be 2.XXX
Add one and you get 3.XXX
round it down and you get 3.

thats because log2 of any number that has only one "1" bit, will be the location of that bit (0 being the first), so anything between 100 and 1000 will be between 2 and 3 for example.

[Quarry]

I think I failed to explain myself but I solved the issue with a very stupidly inefficient snippet

Code:

public static final int getSignificantBitCount(int shift) {
if (LOOKUP_BITS + shift > 8) {
return LOOKUP_BITS + (8 - (LOOKUP_BITS + shift));
} else if (shift < 0) {
return LOOKUP_BITS + shift;
} else {
return LOOKUP_BITS;
}
}

[Evan Balster]

The quickest way to do it would be this one:

Code:

unsigned int v;         // 32-bit value to find the log2 of
register unsigned int r; // result of log2(v) will go here
register unsigned int shift;

r =     (v > 0xFFFF) << 4; v >>= r;
shift = (v > 0xFF  ) << 3; v >>= shift; r |= shift;
shift = (v > 0xF   ) << 2; v >>= shift; r |= shift;
shift = (v > 0x3   ) << 1; v >>= shift; r |= shift;
                                        r |= (v >> 1);

Of course, I doubt this kind of performance is necessary unless you're doing some kind of DSP.

[ThemsAllTook]

I find it really interesting that bitshifts and bit hacks in general are still used for game dev, even now that we have "unlimited processing power"!

Extra processing power opens up a lot of doors beyond writing less efficient code. It's kind of a pet peeve of mine that software tends to get slower at the same pace that hardware gets faster, so nothing ever gets any more responsive from the user's perspective. Some examples of good usage of extra CPU cycles/RAM: Braid's rewind mechanic, Minecraft's huge world of cellular automata. I'm working on a game with online leaderboards, which verifies submitted scores by running a full simulation of the user's play session based on their inputs. For this to work, my game simulation has to be fast enough to verify a full play session in a tiny fraction of how long it took in real time - specifically, a fraction equal to 1 / the maximum number of players submitting scores at once.

Aside from all that, bit twiddling is sometimes more expressive than other, more expensive ways of computing things.

[Quarry]

verifies submitted scores by running a full simulation of the user's play session based on their inputs

Is that overkill or not? It seems like you are trying to do your best to prevent cheating

[ThemsAllTook]

Well, "verifies" is the wrong word. There's no communication of what the client thinks the player's score is; a score submission consists of a set of inputs and a player ID, and the server computes the score on its own by simulating the play session. I've played a couple of games lately where I wished the leaderboards would let me replay the game sessions of the people above me (specifically for speedruns, so I could see the route they took). I wanted to have this feature in the game I'm working on now, and having the score calculated by the server by resimulating it just seemed like a logical extension of that. Preventing cheating is certainly a nice side effect; the only cheats that will be possible are edited inputs or tool-assisted gameplay, and I'm OK with that.

[Gregg Williams]

Networking still has plenty of love for bits and their various uses.