Bit twiddling hacks.

Thorham · 27 April 2012, 20:43

Here's a nice site with a lot of bit wise tricks. May be useful: http://graphics.stanford.edu/~seander/bithacks.html

Photon · 28 April 2012, 03:06

Copied to C forum also. It's a bit ironic to find a C coder publishing code with comparison operators stating it is code without branches

Otherwise, it looks 'keen' and quite like interesting coffee time reading on a rainy afternoon.

Codetapper · 28 April 2012, 06:10

I can't help but feeling that most of those operations on a 68k would be incredibly slow using those techniques!

Especially the one where you can reverse the bits in a byte using 2 multiply operations. Surely a lookup into a 256 byte table of the reversed bytes would be a hell of a lot faster!

Photon · 28 April 2012, 15:52

It is. Most of the things there are terribly obfuscated to anyone who knows how a CPU works. They seem workarounds for someone who is trying to make C work like the CPU works.

The XOR swap is a classic of course, I've only had use for it a couple times though. Its characteristic is that it saves 1 "register" (whether it's a word in memory, temp var, pointer or an actual register). This means it can be used for bidirectional traversal of linked lists as in raytracing, a sorted list of objects, or more generally overload values in a memory cell relative to a known (together with a normal value) saving one cell.

The text for the XOR swap seems confused, says faster on some machines instead of faster with some compiler options set. Maybe a typo, but take comments with a grain of salt.

Samurai_Crow · 28 April 2012, 23:11

Detecting an even power of 2 seemed to be the only useful one I could see. But that one alone is quite useful.

Photon · 28 April 2012, 23:54

Highest bit of positive integer has some use in math libraries. I searched out the fastest known one for ARM when I was coding on the GP2X at one point, and managed to get it down from 15 to 13 instructions IIRC. The best coder had done a decent job actually, those two instructions were a proper mindbender

I think my favorite reads long ago were "Extracting the nth root of a binary number" by L. S. Wo and "The Mathematics of Programming" by C. A. R. Hoare (the one with the XOR swap, but in a bigger context).

27 April 2012, 20:43	#1
Thorham Computer Nerd Join Date: Sep 2007 Location: Rotterdam/Netherlands Age: 47 Posts: 3,753	Bit twiddling hacks. Here's a nice site with a lot of bit wise tricks. May be useful: http://graphics.stanford.edu/~seander/bithacks.html

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
AmigaKit's New Battery Hacks	quarkx	Amiga scene	5	29 October 2012 17:27
Bit twiddling hacks.	Thorham	Coders. C/C++	1	28 April 2012 03:55
REQ: 17-Bit Artwork 2 (1988-04)(17-Bit Software)	Sea7	request.Demos	5	13 May 2011 01:07
8 bit to optimized 6 bit palette histogram improvements needed	NovaCoder	Coders. General	0	14 April 2011 02:13
Memory hacks	Anubis	request.UAE Wishlist	20	07 November 2005 03:28

28 April 2012, 03:06	#2
Photon Moderator Join Date: Nov 2004 Location: Eksjö / Sweden Posts: 5,602	Copied to C forum also. It's a bit ironic to find a C coder publishing code with comparison operators stating it is code without branches Otherwise, it looks 'keen' and quite like interesting coffee time reading on a rainy afternoon.

28 April 2012, 06:10	#3
Codetapper 2 contact me: email only! Join Date: May 2001 Location: Auckland / New Zealand Posts: 3,182	I can't help but feeling that most of those operations on a 68k would be incredibly slow using those techniques! Especially the one where you can reverse the bits in a byte using 2 multiply operations. Surely a lookup into a 256 byte table of the reversed bytes would be a hell of a lot faster!

28 April 2012, 15:52	#4
Photon Moderator Join Date: Nov 2004 Location: Eksjö / Sweden Posts: 5,602	It is. Most of the things there are terribly obfuscated to anyone who knows how a CPU works. They seem workarounds for someone who is trying to make C work like the CPU works. The XOR swap is a classic of course, I've only had use for it a couple times though. Its characteristic is that it saves 1 "register" (whether it's a word in memory, temp var, pointer or an actual register). This means it can be used for bidirectional traversal of linked lists as in raytracing, a sorted list of objects, or more generally overload values in a memory cell relative to a known (together with a normal value) saving one cell. The text for the XOR swap seems confused, says faster on some machines instead of faster with some compiler options set. Maybe a typo, but take comments with a grain of salt.

28 April 2012, 23:11	#5
Samurai_Crow Total Chaos forever! Join Date: Aug 2007 Location: Waterville, MN, USA Age: 49 Posts: 2,186	Detecting an even power of 2 seemed to be the only useful one I could see. But that one alone is quite useful.

28 April 2012, 23:54	#6
Photon Moderator Join Date: Nov 2004 Location: Eksjö / Sweden Posts: 5,602	Highest bit of positive integer has some use in math libraries. I searched out the fastest known one for ARM when I was coding on the GP2X at one point, and managed to get it down from 15 to 13 instructions IIRC. The best coder had done a decent job actually, those two instructions were a proper mindbender I think my favorite reads long ago were "Extracting the nth root of a binary number" by L. S. Wo and "The Mathematics of Programming" by C. A. R. Hoare (the one with the XOR swap, but in a bigger context).

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)