Skip to main content

General

Bitwise Operators ( a = 60, b = 13)

  • a = 0011 1100
  • b = 0000 1101
OperatorDescriptionExample
& Binary ANDOperator copies a bit to the result if it exists in both operands(a & b) (means 0000 1100)
| Binary ORIt copies a bit if it exists in either operand.(a | b) = 61 (means 0011 1101)
^ Binary XORIt copies the bit if it is set in one operand but not both.(a ^ b) = 49 (means 0011 0001)
~ Binary Ones ComplementIt is unary and has the effect of 'flipping' bits.(~a ) = -61 means 1100 0011 in 2's complement form due to a signed binary number.
<< Binary Left ShiftThe left operands value is moved left by the number of bits specified by the right operand.a << 2 = 240 (means 1111 0000)
>> Binary Right ShiftThe left operands value is moved right by the number of bits specified by the right operand.a >> 2 = 15 (means 0000 1111)

Tricks​

  • x & (x-1)will clear the lowest set bit of x
  • (x & (1 << i)) != 0, Get the i^th^ bit
  • x & ~(x-1)extracts the lowest set bit of x (all others are clear). Pretty patterns when applied to a linear sequence.
  • x & (x + (1 << n))= x, with the run of set bits (possibly length 0) starting at bit n cleared.
  • x & ~(x + (1 << n))= the run of set bits (possibly length 0) in x, starting at bit n.
  • (x & (~(1 << i))), clear i^th^ bit
  • x | (x + 1)= x with the lowest cleared bit set.
  • (x | (1 << i)), Set the i^th^ bit
  • x | ~(x + 1)= extracts the lowest cleared bit of x (all others are set).
  • x | (x - (1 << n))= x, with the run of cleared bits (possibly length 0) starting at bit n set.
  • x | ~(x - (1 << n))= the lowest run of cleared bits (possibly length 0) in x, starting at bit n are the only clear bits.

Bit Shift​

Arithmetic Shift​

In an arithmetic shift, the bits that are shifted out of either end are discarded. In a left arithmetic shift, zeros are shifted in on the right; in a right arithmetic shift, the sign bit(the MSB in two's complement) is shifted in on the left, thus preserving the sign of the operand.

Logical Shift​

In a logical shift, zeros are shifted in to replace the discarded bits. Therefore, the logical and arithmetic left-shifts are exactly the same.

However, as the logical right-shift inserts value 0 bits into the most significant bit, instead of copying the sign bit, it is ideal for unsigned binary numbers, while the arithmetic right-shift is ideal for signed two's complement binary numbers.

XOR​

XOR by 1 can work like a toggle switch that turns 1 to 0 or 0 to 1.

  • 0 ^ 1 = 1
  • 1 ^ 1 = 0

Another interesting thing to note is

  • x^0 = x
  • x^x = 0

XOR - Bitwise XOR of N numbers can be calculated as follows : For each bit position (lets say p), if the number of 1's in the binary representation of the involved numbers at position p is odd then the result is 1 else 0. For example, bitwise XOR of three numbers (3, 4, 5) is (011, 100, 101) => (010) = 2. The LSB and MSB has two 1's so result is 0 for those bits. In most languages, [^] operator can be used to find Xor

Method 2 (Efficient method)​

  1. Find the remainder of n by moduling it with 4.
  2. If rem = 0, then xor will be same as n.
  3. If rem = 1, then xor will be 1.
  4. If rem = 2, then xor will be n+1.
  5. If rem = 3 , then xor will be 0.

https://www.geeksforgeeks.org/calculate-xor-1-n

OR - Bitwise OR of N numbers can be calculated as follows : Unlike Xor, if any of the N Number has a 1 in that position (lets say p), then the result at p is 1 else 0. Bitwise OR of (3, 4, 5) is (011, 100, 101) => (111) = 7. All bit positions have atleast 1 number with a 1. In most programming languages [|] operator can be used to find Or

Caching or Indexing​

Caching or Indexing is a technique used to store counts of values which lie in a small range.

1s 2s Complement​

Binary: Plusses & Minuses (Why We Use Two's Complement) - Computerphile