I'm curious to know what usage patterns people have established for themselves to utilize bit shifting in a modern day context such as client/server, web, desktop development. What's a usage of bit shifting in software development other than device drivers, asm?
What bitwise operations / shifting techniques should I be using? What are some algorithms I can reuse?
It really depends on the language, application your developing etc. That being said, I would look at Hacker's Delight. I think it will have what you are looking for.
It was recently discovered that essentially every existing library binary search has had an overflow error when finding the midpoint of an extremely large array. The fix, as implemented in Java, uses a right shift instead of a division. See this article.
Bit shifts, from a "modern" perspective? No... unless you use C or need to fiendishly optimize your app.
Primarily, bit shifts can be used for two things:
A bit shift of 1 is equivalent to dividing by 2 or multiplying by 2 and is much faster. Check it out for yourself : 64>>1==32 and 64<<1==128. In fact, software multiplication/division implementations are often based upon shifts.
ps. All right. There are just my opinion. I know that bitfields are your childhood firend, but please, it's just an opinion.
A major use of bitwise operations these days has got to be for flags words. (Or maybe it's just me? :-) This allows you to use one integer variable to store a number of boolean values in a compact and efficient manner. For this you don't use shifts, just AND and OR operations to test and set different bit values. This can often be used to make code much more efficient (pass one 32-bit integer instead of an array of 32 bools as a parameter; set/clear/toggle/test any arbitrary group of flags in a single bitwise operation, etc)
Another common use is for squeezing data into a more compact format (common in comms, file formats, and applications like embedded controllers where memory is tight). For example, if you have a number that can range between 0 and 25, then you can store it in 5 bits (which is enough to store values 0..31), rather than using a byte (8 bits) or int (often 32 bits or more).
On some architectures/compilers you can speed up operations by replacing multiply/divide operations with combinations of bit shifts and adds - but most modern compilers will do this for you if they spot an opportunity to do so. e.g. "a *= 2" may well be converted to "a <<= 1" if you are using an optimising compiler.
Then there are a number of novel uses that can just be handy sometimes (see Hackers Delight as already mentioned in another answer).
If you're just doing Windows Forms or Web type applications, chances are there won't be any great need to use bitwise ops, but even in these high level environments you can certainly make use of bitwise ops in some cases to make things cleaner and more efficient. Or at the least to make yourself feel a bit less like a plumber, and a bit more like a craftsman :-)
I can think of 3 reasons to do bit-shift operations:
One, as an alternate way to do integer multiplication and division. Left shifting 1 place is equivalent to multiplying by 2; right shifting 1 place is equivalent to dividing by 2. I rarely do this because it makes the code harder to read and understand in order to gain a minor performance improvement. Some compilers are smart enough to do this for you if you are multiplying or dividing by a constant, in which case the gain is zero. The only time I use this technique these days is in something that is very computation-intensive. If I was writing a math library with lots of evaluation of many terms of an infinite series -- like evaluating logs and sines -- I'd probably use something like this. Otherwise, in my humble opinion it's just not worth the price of confusing the next programmer to come along.
Two, In conjunction with ANDs and ORs, as a way to pack multiple logical fields into a single field. Say you have a field whose range of possible values is 0-3 and another which is 0-7. The first could fit in 2 bits and the second in 3. So you could pack both into a single byte. You could put them in with code like:
byte b=(f1<<3) | f2;
You could get them out with:
f2=b & 0x07;
f1=(b>>3) & 0x03;
In the Good Old Days when I worked on computers with 6kB of RAM, I did this sort of thing a lot to cram all the data I needed into memory. Today, when I have a gigabyte on my desktop and multiple gigabytes on the server, the extra complexity of doing this -- read "more places to make mistakes" -- makes it not worth it. If you're writing embedded code for a cell phone or some other very memory-constrained environment, maybe you still need to do stuff like this. I suppose if you're working on a project where you need some truly huge amount of data in memory -- if you're analyzing a human genome or something -- this could be necessary. For the most part, though, knowing how to do this is like knowing how to use a slide rule: an interesting historical relic of little practical value today.
Three, converting between data types when reading from or writing to disk, or communicating with another system with different data storage formats. For example, suppose you want to write a 4-byte binary number to disk. You know that some computers that read this file store integers with the most significant byte first, while others store it with the least significant byte first. To make sure that both can read the data correctly, you must store it and retrieve it in a consistent way. So you pick one byte order and force it to store that way. Like:
for (int p=0;p<4;++p)
{
byte b=i & 0xff;
out.write(b);
i=i>>8;
}
This is about the only time I use bit-shifting these days.
Here's a neat application of bit-shifting and masking that I used to manipulate a buffer of pixels.
bool pBuffer::GetPixel(unsigned int x, unsigned int y)
{
char c = blocks[((y * width) + x) / 8];
return (bool)((c >> (((y * width) + x) % 8) & 1));
}
Width and height are the known dimensions of the supposedly 2-Dimensional array. The array (blocks[]) is only one dimensional, however. Each bit in a char represents a pixel, which is on or off.
This functionality was used in my implementation of a convex hull algorithm, in order to allow the user to paint a 2D level on the screen using minimal amounts of memory.
The point is, if you know how bits are representing your data, you can do sneaky things to that data by bit-shifting.
I guess The Art of Computer Programming, Vol. IV, Fasc. 1 will be right up your alley.
They can be very useful with bit mask enumerations e.g.
enum flags {
IMAGE_FLIP_HORIZONTAL =1 << 0,
IMAGE_FLIP_VERTICAL =1 << 1,
IMAGE_DESATURATE =1 << 2,
IMAGE_INVERT =1 << 3,
IMAGE_NOALPHA =1 << 4
};
Then you may provide an API which allows
loadImage("pirate.gif", IMAGE_DESATURATE | IMAGE_FLIP_HORIZONTAL);
If you ever use libpng there is a chance you are using this type of enum. In pngread.c there is a block at the end of the file which uses masks like this to apply transformations:
#if defined(PNG_READ_INVERT_SUPPORTED)
/* invert monochrome files to have 0 as white and 1 as black
*/
if (transforms & PNG_TRANSFORM_INVERT_MONO)
png_set_invert_mono(png_ptr);
#endif
#if defined(PNG_READ_BGR_SUPPORTED)
/* flip the RGB pixels to BGR (or RGBA to BGRA)
*/
if (transforms & PNG_TRANSFORM_BGR)
png_set_bgr(png_ptr);
#endif
#if defined(PNG_READ_SWAP_ALPHA_SUPPORTED)
/* swap the RGBA or GA data to ARGB or AG (or BGRA to ABGR)
*/
if (transforms & PNG_TRANSFORM_SWAP_ALPHA)
png_set_swap_alpha(png_ptr);
#endif
#if defined(PNG_READ_SWAP_SUPPORTED)
/* swap bytes of 16 bit files to least significant byte first
*/
if (transforms & PNG_TRANSFORM_SWAP_ENDIAN)
png_set_swap(png_ptr);
#endif