Graal Forums - Bit Operations Tutorial / Reference

I had this on file for a while, made back when I actually coded actively on Graal, and I thought I'd post it to give Graal developers some references on how to use and implement bit values. Cheers.
Some of the information may be incorrect, but most of it is correct. Hopefully y'all can learn something from it. If you did, be sure to rep! :)
_____________________________

First off, we need to understand how binary works. Binary, as you all know, is a series of base 2 (0 and 1) numbers indicating whether the underlying value is active. The underlying values are powers of two, in base 10, as described below:

NPC Code:

  256     128     64     32     16     8     4     2    1

Therefore, the binary string 100101011 would be:

NPC Code:

BASE10:    256     128     64     32     16     8     4     2    1

BINARY:      1       0      0      1      0     1     0     1    1

Adding up the 1 values (1, 2, 8, 32, and 256) gives us 299. It's as simple as that. Binary strings can go on indefinitely, provided you have enough space and enough patience to use the larger version of the numbers.

Now, on to the operators.

-- Bitwise Shifts (a<<n and a>>n)
Bitwise shifts do exactly what they sound like they do - they shift the numbers n spots to the left (<<) or right (>>). Therefore, in the above example, 100101011, would give the following values when bitshifted:

NPC Code:

100101011 >> 1 = 010010101

100101011 << 1 = 001010110

-- Bitwise Basic Operators (Or [|], And [&] and Exclusive Or [xor])
These operations require knowledge of a few truth tables to be effective:

NPC Code:



bit1     bit2      or (|)      and (&)      xor (xor)

0        0         0           0            0

1        0         1           0            1

0        1         1           0            1

1        1         1           1            0

So, let's go down the list.

| (bitwise OR) sets a bit to 1 if one or both of the corresponding bits in its operands at 1, and to 0 if both of the corresponding bits are 0. In other words, | returns 1 in all cases except where the corresponding bits of both operands are 0. The resulting bit pattern is the "set" (1 or true) bits of any of the two operands. This property is used to "set" or "turn on" a "flag" (bit set to one) in your flags or options variable regardless of whteher that flag was set previously or not. Multiple flag bits can be set if a combo MASK is defined.

PHP Code:


		
			
// to set or turn on a flag bit
flags = flags | MASK;
// or, simpler,
flags |= MASK;

& (bitwise AND) sets a bit to 1 if and only if both of the corresponding bits in its operands are 1, and to 0 if the bits differ or both are 0. In other words, one ANDed with any bit is that bit, and a zero ANDed with any bit is a zero. This operator is used to check the state of a flag in your flags variable. When you AND your flags variable with the MASK, all zeros in the mask will return 0 for the corresponding position in flags and all ones in the mask will return whatever the corresponding bit is set to in your flags variable. Therefore, the bitwise AND operator evaluates to MASK itself only if the MASK flags are also set in the flags variable.

PHP Code:


		
			
// To check the state of a flag bit
if (flags & MASK == MASK)  // or, in GScript, you can simply omit ==MASK as every variable >=1 is treated as "true" in if statements.
  // flag is set or turned on
else
  // flag is not set or is turned off

xor (bitwise XOR or exclusive OR) sets the bit to 1 where the corresponding bits in its operands are different, and to 0 if they are the same. Even 1 xor 1 evaluates to 0 unlike the regular bitwise OR. A bit pattern XORed with itself returns zero (because some bit values returned zero). The bitwise XOR is used to toggle the flag bits of a MASK in your flags variable. It means that, if a flag bit was set in flags, XORing with its MASK will unset it. If it was not set XORing will set it. This is different from turning a flag bit on or off, regardless of its prior state (which is accomplished using | and & ~).

PHP Code:


		
			
// To toggle a flag bit (on if it was off, off if it was on)
flags = flags xor MASK;

~ (Bitwise NOT) takes only one parameter and inverts each bit in the operand, changing all the ones to zeros and zeros to ones. This is useful when 'unsetting' or 'turning off' a flag.

PHP Code:


		
			
// To unset or turn off a flag bit
flags = flags & ~MASK;
// or, simpler,
flags &= ~MASK;

Now, you may be asking, "what possible use is there for a bit mask?" There are a few, consider the following:

- XOR can swap two variables without using an intermediate, temporary variable which is useful if you are short on available RAM or want that sliver of extra speed.

Usually, when not using XOR, you would do:

PHP Code:


		
			
temp.c = a;
a = b;
b = temp.c;

Using XOR, no "temp.c" is needed:

PHP Code:


		
			
a = a xor b;
b = b xor a;
a = a xor b;

- Bit masks can be useful if you want to store data in a smaller amount of space. Consider this:
Let's say that a user can be granted four types of permissions - View, Add, Edit and Delete.
It doesn't make sense to allow a user to add, edit, or delete tables or rows if the user cannot
view them. What we need are sets of valid permissions that a user may be granted.

PHP Code:


		
			
const PERMISSION_VIEW = 1;
const PERMISSION_ADD = 2;
const PERMISSION_EDIT = 4;
const PERMISSION_DELETE = 8;

Stored in a file, regular method would probably be:

NPC Code:

userpermissions=1,2,4,8

Or possibly,

NPC Code:
userpermissions=VAED

But, using Bit masks, you can use PERMISSION_VIEW | PERMISSION_ADD | PERMISSION_EDIT | PERMISSION_DELETE to come up with

NPC Code:
userpermissions=15

You just saved a few bytes of data, not very significant in a small file, but if you have a large amount of permissions or a large amount of users, or both, bit masks can be invaluable to ensure small size.

By the way, to check if a user has a permission, simply do this:

PHP Code:


		
			
if (userpermissions & PERMISSION_VIEW)
  // Yep!  He does.

A few examples where bit shifting is quite useful:

- Converting a hexadecimal color code (similar to HTML color codes) to RGB:

PHP Code:


		
			
public function convertHexToRGB(hex)
  {
    if (hex == 0) return {0, 0, 0};
    r = hex >> 16;
    hex -= (r << 16);
    g = (hex / 64);
    b = hex - (g << 8);
    return {r, g, b};
  }

Try it! convertHexToRGB(0xFFFFFF) = {255, 255, 255};

- Converting 4 bytes of data into an integer type (C# alert! Will not work in GScript! [No support for streaming?])

PHP Code:


		
			
byte[] ch = new byte[4];
  stream.Read(ch, 0, 4);
  
  if ((ch[0] | ch[1] | ch[2] | ch[3]) < 0) throw new IOException("EOF");
  return ((ch[0] << 24) + (ch[1] << 16) + (ch[2] << 8) + (ch[3]));