Skip to content

Latest commit

 

History

History
99 lines (79 loc) · 2.33 KB

bit-operators.md

File metadata and controls

99 lines (79 loc) · 2.33 KB
Raw

Bit Operators

  • Leading zeros 0 (i.e., to the left) are meaningless

~ NOT

  • Invert a bit
  • Examples:
    • ~0 = 1
    • ~1 = 0
    • ~0111 = 1000
    • ~100 = 011
  • In Java, ~ inverts an int and not single bits, so:
int b = 0b10;
~b == 11111111111111111111111111111101

& AND

  • Results in 1 in each position if the corresponding first bit and second bit are 1, otherwise 0.
  • Enables to find if a certain bit in a number contains 1 or 0. Can be considered like multiplying all bits.
  • Examples:
    • 10 & 11 = 10
    • 0011 & 0010 = 0010

| OR

  • Results in 1 in each position if the corresponding first bit or second bit are 1, otherwise 0.
  • Enables to set a specific bit to 1.
  • Examples:
    • 10 | 11 = 11
    • 0011 | 0010 = 0011

^ XOR

  • Exclusive OR – results in 1 in each position if the corresponding first bit or second bit are 1, but not both, otherwise 0.
  • Enables to compare two bits – 1 means they are different, 0 means they are the same.
  • Can be used to invert selected bits in a register. Any bit can be toggled by XOR-ing it with 1.
  • XOR-ing a value against itself yields zero.
  • Examples:
    • 0101 ^ 0011 = 0110
    • 0010 ^ 1010 = 1000
  • XOR can be used for "backup":
    • Calculate a and b's XOR: x = a^b
    • If needed, recover a: a = b^x
    • If needed, recover b: b = a^x

<< Shift Left

  • Add n 0 bits to the right.
  • A left arithmetic shift by n is equivalent to multiplying the number by 2^n.
  • For example: 10111 << 1 = 101110

>> Shift Right

  • Remove n bits from the right (0 or 1).
  • A right arithmetic shift by n is equivalent to dividing by 2^n.
  • For example: 10010111 >> 1 = 1001011

See also Java section on Bit Arithmetics/Operations and Data Structures code examples for BitSet.

Binary Numbers

0 = 0
1 = 1
10 = 2
11 = 3
100 = 4
101 = 5
110 = 6
111 = 7
1000 = 8
1001 = 9
1010 = 10
1011 = 11
1100 = 12
1101 = 13
1110 = 14
1111 = 15
10000 = 16
...

10010110
^      ^
|      |------- bit 0
|
|-------------- bit 7

Having a 1 in the k-th bit, means that the decimal number is comprised of 2^k. For example, for the above number:

2^7 + 2^4 + 2^2 + 2^1 = 150