Bitwise Operations

<aside> 💡 Integral Data Types: long, int, short, char, unsigned

</aside>

• Can only be applied to integral datatypes
• undefined behavior is when the shift amount is < 0 and ≥ wordsize

<&> - A&B = 1 when both A = 1 or B = 1
<~> - ~A = 1 when A = 0 (Basically Flips all of the bits)
<|> - A|B = 1 when either A = 1 or B = 1
<XOR> - A^B = 1 when either A = 1 or B = 1 but not both

// Sample Bitwise Tricks

~x + x = -1
~x + x + 1 = 0
~x + 1 = -x

int bit = ((1 << i) & num);
return !!bit; // returns bit

return ((1 << i) | num); // sets a bit

// bit branching if (test) a: output = 1 else output = b;
mask = ((!!test << 31) >> 31);
output = (mask & a) | (~mask & b);

~x is the same thing as (-x)-1

x >> 31 & 1 // Tells if it is negative
(x >> 31) << 31 // clears all of the positive bits

Representing and Manipulating Sets with Bits

• Can represent sets of 8 or lower using bytes for instance {0, 3, 5, 6} → 01101001 (76543210) in that order specifically
  • Like each of the numbers represents that in reverse order
• This is useful because we can do operations on these as well

Comparing Bitwise Tricks

(x >= 0) || (x < ux) // False (eg. x = -1.  Comparison x < ux is never true.)

Datalab Implementations

// isNegative: Returns 1 if x < 0, 0 otherwise
int func1(int x) {
    return (x>>31) & 0x1;
}

// isTmin: Returns 1 if x == Tmin, 0 otherwise
int func2(int x) {
  return (!!x) & (!(x+x));
}

// isZero: Returns 1 if x == 0, and 0 otherwise
int func3(int x) { 
  return !x;
}

// isTmax: Returns 1 if x == Tmax, 0 otherwise
int func4(int x) {
    int nx = ~x;
    int nxnz = !!nx;
    int nxovf = !(nx+nx);
    return nxnz & nxovf;
}
int tmax(void)
{
  return ~(0x01 << 31);
}

// Does BitXOR
int bitXor(int x, int y) 
{
  return ~(~x & ~y) & ~(x & y);
}

// isNonZero: Returns 1 if x!=0, 0 otherwise
int func5(int x) {
  int minus_x = ~x+1;
  return ((minus_x|x) >> 31) & 1;
} 

int isNotEqual(int x, int y) 
{
  return !!(x^y);
}

int sign(int x) 
{
  return ((!!(x)) | (x >> 31));
}

int conditional(int x, int y, int z) 
{
  x = !x << 31;
  x = x >> 31;
  return (~x & y) | (x & z);
}

int replaceByte(int x, int n, int c) 
{
  int bytes_shift = (c << (n << 3));
  int mask = 0xFF;
  mask = mask << (n << 3);
  return (~mask & x) | bytes_shift;
}

int isAsciiDigit(int x) 
{
  int first_d = !((x & ~0x0F) ^ 0x30);
  int second_d = !(((x & 0x0F) + 0x06) & 0xF0);
  return first_d & second_d;

}

int leastBitPos(int x) 
{
  int negation = ~x + 1;
  return (x & negation);
}

int rotateLeft(int a, b)
{
	p = a << b
	q = a >> (33+~b)
	mask = ~0 << b;
	Q &= ~mask
	return P|Q;
}

int abs(x)
{
	int m >> 31;
	return (x^m)+ ~m+1
}