Sign in to follow this  
h3ro

Use for binary operations?

Recommended Posts

Hallo, How much are binary arithmetic used? Can they be used to preform normal arithmetic operations? I know that shifting left and right is the same as dividing and multiplying, but what are the uses for or, and and xor? Regards,

Share this post


Link to post
Share on other sites
OR and AND are used all over the place for bitfield operations (where you store multiple small values inside a larger integer variable).

XOR isn't used quite as much, but it does have some fun uses (CRC/hash generation, simple encryption, x86 branchless abs(x) idiom).

Some binary operations are used for x86 'divide by arbitrary constant' idioms as well.

Share this post


Link to post
Share on other sites
Quote:
Original post by h3ro
but what are the uses for or, and and xor?

For example if you want to ensure the result of an operation fits in 10 bits, you can do

result = (a+b+c) & 1023;

where "& 1023" masks of all bits except the 10 least significant ones.

Or if you want to find the next multiple of 4 of a number:
0 -> 0
1 -> 4
2 -> 4
3 -> 4
4 -> 4
5 -> 8
6 -> 8
7 -> 8
8 -> 8
9 -> 12

You can do that with addition and AND:

int next_multiple4(int number)
{
return (number + 3) & ~3;
}

where "& ~3" sets the two least significant bits to 0.

Share this post


Link to post
Share on other sites
The & (and) and | (or) operators are quite common in the Win32 and DirectX APIs (among, I'm sure, lots of others) to comine groups of options.

For example:


DWORD FVF=D3DFVF_XYZ | D3DFVF_NORMAL | D3DFVF_TEX1;


If, for the sake of the argument, these values were defined like (which they probably aren't):


const DWORD D3DFVF_XYZ=1;
const DWORD D3DFVF_DIFFUSE=2;
const DWORD D3DFVF_NORMAL=4;
const DWORD D3DFVF_TEX1=8;


then their bit representations (in 8-bit to make it easier to type) are:


1 - 00000001
2 - 00000010
4 - 00000100
8 - 00001000


If you bitwise OR two values together, the result has a 1 in any column where either or both of the two value's corresponding bits are true.

So 1 | 4 is


00000001
00000100
--------
00000101


and that result | 8 is:


00000101
00001000
--------
00001101



It is then possible to test for the presence of a set bit with &, like:


if(FVF & D3DFVF_TEX1) // FVF has one set of texture coordinates


This depends on the fact that doing a bitwise and with a mask sets each result's bit if, and only if, both corresponding bits in the arguments are true.


00001101
00001000
--------
00001000


Since the fourth bit, which is the only one set in the mask D3DFVF_TEX1 (or 8), the result will only be non-zero if the fourth bit in FVF is also set.


An interesting property of XOR is that if you XOR a value against a second value, the result XOR'd against the second value will give you back your original value:


00100101 - A
10110110 - B
--------
10010011 - C

10010011 - C
10110110 - B
--------
00100101 - A


This makes XOR very useful in encryption. As a simple example, you can XOR every character in a text string against a given number. If you then XOR each encrypted character against the code number, you get the original text file back, but if you need to know the code number to know what to XOR against.

Share this post


Link to post
Share on other sites
The through is that im working on my own 2d graphics api (colours/alpha blending), and I cant say that I have found many places to use bit shifting.

Does anyone know of any tips that apply to 2d graphics?

Share this post


Link to post
Share on other sites
Quote:
Original post by h3ro
The through is that im working on my own 2d graphics api (colours/alpha blending), and I cant say that I have found many places to use bit shifting.

Does anyone know of any tips that apply to 2d graphics?
Yes.
The good news is that if you're not using bit-shifting and other bitwise operations much, then you probably have a huge potential for performance optimisations later.

e.g. Here's a function that accurately converts a colour value from 16-bit colour to 32-bit colour; Nothing but SHIFTs, ORs and ANDs.
unsigned long X1R5G5B5toARGB32(unsigned short o) {
const unsigned long r = o&0x7C00, g = o&0x03E0, b = o&0x1F;
return (unsigned long)((((((r>>7)|(r>>12))<<8) | (g>>2)|(g>>7))<<8) | (b<<3)|(b>>2));
}

Share this post


Link to post
Share on other sites
I run into use for binary operators all the time when doing networking, cryptography, or trying to pack data down into smaller sizes (which is often the case with the networking).

Binary operations often don't have much use or value to you until you are working on a bit level. The most common and probably most simple example is combining flags with the OR operator like mentioned previously. On the other side, to check which flags are set, you would use the AND operator. Like Nypyren mentioned, you will run into AND and OR all over the place.

Either way, its important to know how they work. :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this