The Allegro Wiki is migrating to github at https://github.com/liballeg/allegro_wiki/wiki

Bitwise operator

From Allegro Wiki
Jump to: navigation, search

Overview

Bitwise operations work on data considering the data as an array of incoherent bits. So, a common 64-bit integer is considered as 64 sequential bits. As shown, most bitwise operators are binary (work with two arguments). The operations correspond to single instructions commonly found in CPU's. In C it can work on any built-in data-type, but often it only has results that can be interpreted properly, when used on unsigned integers.

Binary values

Note that in a binary number, each digit represents a power of 2. An exception is the "sign bit" in signed data-types. Often when defining flags an octal or hexadecimal notation is used to emphasize and clarify this relation. In C you can for instance define the following, to address the first 4 bits of a data-type. <highlightSyntax language="cpp"> enum Flags1 { flag1 = 0x1, flag2 = 0x2, flag3 = 0x4, flag4 = 0x8, flag5 = 0x10 }; </highlightSyntax>

Basic functionality

You can check the wikipedia entry on bitwise operators.

The quick overview below shows the operators as they are in C and C++, and an example on two fictional variables, which are only 4 bits long. These variables are shown in binary format for clarity.

Bitwise operators in C and C++
NameOperatorExample
Complement ~ ~1001 yields: 0110
OR | 1001 | 1101 yields: 1101
XOR (Exclusive-OR) ^ 1001 ^ 1101 yields: 0100
AND & 1001 & 1101 yields: 1001
LSHIFT (left-shift) << 1001 << (int)1 yields: 0010
RSHIFT (right-shift) >> 1001 >> (int)1 yields either: 0100 , or 1100

Note that in C the binary operator appended by "=" carries out the operation on, and saves the result in, the left-value. Also note the shift operators are technically not bitwise operators. But they are often used for bitwise manipulation, and thus mentioned for reference.

Practical aplications

Flags and masks

If you have a (great) number of binary values you can use the individual bits of a variable to represent them. Binary values in this context are often referred to as "flags". Flags are either "set" or "unset". Data with flags is often used by hardware, communication protocols or error return values. You can check or set flags with binary operations.

Setting a value

Use OR to set a flag. These two lines both set FLAG in DATA: <highlightSyntax language="cpp"> DATA = DATA|FLAG; DATA |= FLAG; <highlightSyntax> If you know for sure the value is unset, you could also flip it.

Unsetting a value

Use AND with the COMPLEMENT to unset a flag. These two lines both turn FLAG in DATA off: <highlightSyntax language="cpp"> DATA = DATA & ~FLAG; DATA &= ~FLAG; <highlightSyntax> If you know for sure the value is set, you could also flip it.

Flipping a value

Use XOR to flip a flag from on to off, or from off to on. These two lines both toggle the value of FLAG in DATA: <highlightSyntax language="cpp"> DATA = DATA ^ FLAG; DATA ^= FLAG; <highlightSyntax>

Examples

Using flags

<highlightSyntax language="cpp"> //Using flags as conditions

  1. define FLAG_1 1
  2. define FLAG_2 2
  3. define FLAG_3 4 /* these are powers of two */

//<etc>

//...

int FlagField = FLAG_1 | FLAG_2; // FlagField has flags 1 and 2 set

//...

if(FlagField&FLAG_3) { // this code is executed iff flag 3 is set }

if(FlagField&FLAG_2) { // this code is executed iff flag 2 is set }

if(FlagField&(FLAG_1|FLAG_2)) { // this code is executed if either FLAG_1 or FLAG_2 is set }


if(NewVar^OldVar&NewVar&FLAG_1) { // executes only if flag 1 is set in NewVar but not in OldVar }

OldVar = NewVar; </highlightSyntax>

Binary property subsets

One way to use bits in numbers is as a set. Suppose that you have ten items and want to represent subsets of those items. Simply use the first ten bits of an int, where 1 means its included and 0 means it is not included. To check if a particular item is included: subset_flags & (1 << index) Flip it using subset_flag ^= (1 << index) However, the neatest part is iteration for(int subset = 0; subset < ( 1 << count_of_items_in_set);subset++) This will iterate through all possible subsets. But due to nature of order through which it will go through the possiblities, for every set under consideration, all possible subsets will have already undergone consideration.

I.e. for the subset

1101

All of the following are before it:

1100
1001
0101
0001

Optimization

Bitwise operations are very fast. They can be used to replace more expensive operations.

Modulo power of two

A modulo of power of two can be achieved by performing an AND operation with the divisor-1. For instance: var%8 yields the same as var&7. The AND operation is on its own on most computers faster than the modulus operation. This technique is applied often with allegro's fixed type as argument for rotate_sprite, where you need the value to wrap around 256. With other words where you need modulo 256.

Power of two check

To quickly assure a number is a power of two or that only one or no flags are set, you can use the following method. Note that a extra condition is required to exclude "0" / no flags set. <highlightSyntax language="cpp"> if((number-1)&number){ //Number is not a power of two or multiple flags set } else{ //Number is a power of two (including 0), or one or no flags set } </highlightSyntax>

The XOR swap

An outdated way of swapping two values. The crux is it only uses the two values being swapped, without the use of an extra intermediary piece of data. Apart from sparing resources (a single register), sometimes it even was faster. If we start with two variables x and y, with x = a and y = b then the following diagram shows the swap:

xy
ab
x ^= y
a^bb
y ^= x
a^bb^a^b
x ^= y
a^b^b^a^bb^a^b

The XOR operation is commutative and associative. That means we can choose any order of these operations and still have the same result. Furthermore for any value i there is: i ^ i = 0; And 0 is the identity of this operation: i ^ 0 = i. In conclusion the final result is:
x = a^b^b^a^b = (a^a) ^ (b^b) ^ b = 0 ^ 0 ^ b = b
y = b ^ a ^ b = b ^ b ^ a = 0 ^ a = a

So the values are swapped. Speed tests of XOR swap.

Examples

Bob's page of mildly usefull but still neat code snippets

Article Contributors: Thomas Harte, Evert, SiegeLord, bamccaig, Peter Wang, Edgar Reynaldo, anonymous, Vanneto, Roy Underthump, Winston Ewert.

Entry in "Discussion Thursdays?" Reference:Bob's page of mildly usefull but still neat code snippets