bitwise-operators

Bitwise Operators

Bitwise Operators

Bitwise operators are used to perform operations on bits. Unlike logical and relational operations, bitwise operations do not return boolean true or false, but rather the value of the operation's result:

' bitwise operator & (and)
n = 5 & 9; 'n = 1

In the above example the result is 1 because the bits of both operands are compared with the bitwise “and” (&) operator. If the corresponding bits are both set (1), the resulting bit is also set. In all other cases the resulting bit is unset (0):

00000101 = 5
00001001 = 9
------------
00000001 = 1

So bitwise operators do the same as logical operators, but on a bit-level, whereby “1” is considered “true” and “0” is considered “false”.

SharpBASIC has the following nine bitwise operators:

&    bitwise 'and'
|    bitwise 'nor'
?    bitwise 'or'
!    bitwise 'xor'
&&   bitwise 'eqv'
!!   bitwise 'imp'
~    bitwise 'not'
<<   shift left
>>   shift right

The following truth table applies to the bitwise operators:

x    y      x & y    x | y    x ? y    x ! y    x && y    x !! y    ~x
1    1        1        0        1        0        1         1        0
1    0        0        0        1        1        0         0        0
0    1        0        0        1        1        0         1        1
0    0        0        1        0        0        1         1        1

Examples of bitwise operations with a mask isolating the first 8 bits:

r = (a | b) & #hFF;   ' bitwise nor
r = (a && b) & #hFF;  ' bitwise eqv
r = (a !! b) & #hFF;  ' bitwise imp

If a = 5 and b = 9, the result would be:

00000101 = 5
00001001 = 9
------------
11110010 = 242 (nor)
11110011 = 243 (eqv)
11111011 = 251 (imp)

The following programming example counts leading and trailing zero's:

example 1

' SharpBASIC count leading and trailing zero's, bitwise programming example
' ------------------------------------------------------------------------
option strict;

incl "lib/sys.sbi";

decl func clz(x:int): uint;
decl func ctz(x:int): uint;

main do
  print(clz(4));
  print(ctz(48));
end

func clz(x:int): uint
' count leading zero's
  dim msb: int;
  dim b: uint8;
  dim n: uint = 0;
do
  ' loop through 32 bits while bit is zero
  loop msb = 1 << 31 do
    ' left-shift while zero
    while (x & msb) == 0; x:<<;
    ' count it
    n:++;
  end
  ' return count
  clz = n;
end

func ctz(x:int): uint
' count trailing zero's
  dim n: uint = 0;
do
  ' loop while bit is zero
  loop do
    ' right-shift while zero
    while (x & 1) == 0; x:>>;
    ' count it
    n:++;
  end
  ' return count
  ctz = n;
end

Output:

The next example demonstrates various bitwise operations, including populated bit count and groups of populated bits count.

example 2

' SharpBASIC populated bits, bitwise programming example
' ------------------------------------------------------
option strict;

incl "lib/sys.sbi";

decl func PopBits(x: int): int;
decl func BitIsls(x: int): int;

dim x, n: int = 0;

main do

  ' bit n
  n = 2;

  ' set bit n
  x = (1 << n) ? x;
  print(x);                             ' 4

  ' clear bit n
  x = ~(1 << n) & x;
  print(x);                             ' 0

  ' flip bit n
  x = (1 << n) ! x;
  print(x);                             ' 4

  ' convert trailing zero's
  x = (x - 1) ? x;
  print(x);                             ' 7

  ' count populated bits
  n = PopBits(x);
  print(n);                             ' 3

  n = BitIsls(x);
  print(n);                             ' 1

end

' count populated bits (bits that are set to 1)
func PopBits(x: int): int
  dim n: int = 0;
do
  loop do
    until x == 0; n:++;
    x = x & (x - 1);
  end
  PopBits = n;
end

' count groups of populated bits
func BitIsls(x: int): int
do
  BitIsls = ((x & 1) + PopBits((x ! (x >> 1))) / 2);
end

The next example demonstrates addition through bit shifting:

example 3

' SharpBASIC addition, bitwise programming example
' ------------------------------------------------
option strict;

incl "lib/sys.sbi";

decl func bitw_add(a:uint, b:uint):uint;

dim x, y, z: uint;

main do

  x = 1;
  y = 3;

  z = bitw_add(x, y);
  print(z);

end

func bitw_add(a:uint, b:uint):uint
  dim carry:int;
do
  loop do
    while b <> 0;
    ' carry value of a and b
    carry = a & b;
    ' sum goes in a
    a = a ! b;
    ' left-shift carry by 1 goes in b
    b = carry << 1;
  end
  ' return the sum
  bitw_add = a;
end

Output:

Same as example 3, using recursion:

example 4

' SharpBASIC addition 2, bitwise programming example
' --------------------------------------------------
option strict;

incl "lib/sys.sbi";

decl func bitw_add(a:uint, b:uint):uint;

dim x, y, z: uint;

main do

  x = 1;
  y = 3;

  z = bitw_add(x, y);
  print(z);

end

func bitw_add(a:uint, b:uint):uint
do
  if b <> 0 do
    bitw_add = bitw_add(a ! b, (a & b) << 1);
  else do
    bitw_add = a;
  end
end

Output:

Table of Contents