12. Binary Expression, Bitwise Operator

SungJunEun·2021년 12월 10일
0

33 Key JS Concepts

목록 보기
12/14
post-thumbnail

Articles


Bits

Bits are binary digits consists of 0 & 1, which is the basic unit of data in computer.

Bitwise Operators

& (AND)

Return 1 if both compared bits are 1s.

| (OR)

Returns 1 if either of compared bits is 1.

^ (XOR)

Returns if compare bits have only single 1.

~ (NOT)

Flips the bits.

a<<b (left shift)

Shifts a in binary representation for b bits to left, add 0 for missing ones.

a>>b (right shift)

Shifts a in binary representation for b bits to right.


Two's complement

two's complement is a way to express negative numbers in binary expression. The leftmost bit represents the sign, if it is 1, it means that number is negative.

For example,

  • 10111 = -16 + 4 + 2 + 1 = 9

  • 10011 = -16 + 2 + 1 = -13, while

  • 01001 = 8 + 1 = 9

  • 01101 = 8 + 4 + 1 = 13

The interesting part is that negative version of certain number is obtained by flipping each bit and then adding one.

For example, in the case for 13...
13 = 01101(2)
~13 = 10010(2)
~13 +1 = 10011(2) = -16 + 2 + 1 = -13

-X = ~X +1, while, X is base 2


How to express number in base 2

using parseInt

parseInt(1111,2) // 15

using binary literals (ES6)

let a= 0b111;
console.log(a); // 7

(0o prefix is for octal literals)


Real world implementation of binary expression

Case1. Data of which student returned his homework

Let's say I'm the math teacher of class consists of 5 students. I want to store data which student returned his homework or not.

Using Array

One way is using array. We can use true for who returned his homework, and false for not returned yet. So, initial state for array would be like this.

const Data = [ false, false, false, false, false];

Let's say student of index 0, 2 returned his homework.
Then you should iterate the array and modify the false to true of responding index.

for(i=0;i<Data.length;i++){
   if((i == 0) || (i == 2)){
      Data[i] = true;
   }
}

console.log(Data); // [ true, false, true, false, false]

It has time complexity of O(n).

Using binary expression & bitwise operator

Instead of using array, lets use binary expression. Instead of true, we use 1 and false for 0. So, initial state would be like this.

let Data = 0b00000;

It is a single number, compare to array, it save lots of memory if we think the number of students become larger.

For same case of updating, we can use | bitwise operator. To update the state of student of index 0, 2...

Data = Data | 101000 ;
console.log(Data); // 101000

Let's say we want the list of students who didn't returned homework yet.

const yetRetured = ~Data;
console.log(yetReturned); // 010111

If new student was added to class,

Data = Data << 1 ;
console.log(Data); // 1010000

It's way more simple!


Case2. Checking flags

Let' say we operate website and want to check whether the state of user satisfies multiple flags. For example,

  • flag A = 'Is user authenticated?'

  • flag B = 'Is user in unprohibited region?'

  • flag C = 'Is user human(not bot)?'

  • flag D = 'Is user's payment is accepted?'

Similar to Case 1, we can use array and multiple if statements. But it's way more easier and simpler to use binary expression. Let's match one-to-one with flags and binary digits.

  • flag A = 0001(2) = 1

  • flag B = 0010(2) = 2

  • flag C = 0100(2) = 4

  • flag D = 1000(2) = 8

Then we can check user's state as an integer with following function.

function raiseflag(binary){
  const flagA = 0b0001;
  const flagB = 0b0010;
  const flagC = 0b0100;
  const flagD = 0b1000;
  const flags = [];
  
  if(binary & flagA) {
    flags.push('flagA');
  }
    if(binary & flagB) {
    flags.push('flagB');
  }
    if(binary & flagC) {
    flags.push('flagC');
  }
    if(binary & flagD) {
    flags.push('flagD');
  }
  return flags;
}

console.log(raiseflag(10)); // ["flagB", "flagD"]
profile
블록체인 개발자(진)

0개의 댓글