Forem: Andrew Lederman

Bitwise Operators in JavaScript

Andrew Lederman — Fri, 31 Mar 2023 16:41:16 +0000

Binary numbers can be stored and represented with different amounts of bits. For instance, in JavaScript a single number in decimal is technically stored in memory as a 64-bit binary number. That's a lot of leading zero's...In many cases this is fine, but there are cases where we may want to conserve memory and use our alotted bits more intentionally.

Let's say we are storing the decimal number 10 as a byte of data.

00001010 = 10

Technically we are using 8 bits to represent a single number value. If we think of each bit as a boolean value (on/off, true/false) instead of an actual number, a lot of real-world applications open up for us. Let's say we have a user who can have different levels of permission to access files. The user's permissions might be stored in an object like so:

{
   readPermission:true,
   writePermission:false,
   admin:false,
}

This works fine, but another option is to assign the user a single decimal number, stored as binary, and use each individual bit to represent one of these flags instead! We would just need to be able to query and update each bit individually depending on our use case. Manipulating bits on this level requires bitwise operators.

Bitwise Operators

Bitwise operators take two values and compares them, outputting a new value from the computation. In JavaScript we generally run bitwise operations against two decimal numbers, which are then converted into binary values behind the scenes. It is also technically possible to work with binary numbers directly in JavaScript using Binary Literals which we will look at in a later post.

JavaScript stores decimal numbers in memory as 64-bit binary values. When a bitwise operator is used, each initial decimal value in the computation is converted into a 32-bit binary number in Two's Complement form, the computation is executed, then the result is converted back into 64-bits and finally returned as a decimal number.

Since it is possible to use individual bits to represent real world states (like user permissions), we can think of these operators as allowing us to query and determine state.

Let's take a look at the bitwise operators available to us and the actions they allow us to perform on binary numbers...

AND (&)

The bitwise AND operator takes two binary numbers and combines them, comparing each set of digits in a column and outputs a 1 only if both inputs are 1. In all other cases the AND operator will return 0.

What can we do with this? You can think of the AND operator as allowing us to access or read specific bits within a binary word. Let's look at an example:

  10 & 7

  00001010 = 10
& 00000111 = 7
-----------
  00000010

Any column with a 1 in the second number allows the original value to pass through or be read, while a 0 in the second number will turn off or mask that value. This is why the 1 in the 8's column is turned off in this example.

It's important to understand that with bitwise operators, we're not really concerned with the result in terms of base 10 values, we're not actually adding numbers. We're executing a computation to determine the state of a specific set of bits.

OR (|)

The OR operator returns 1 if either bit in the computation is 1. An easier way to think of this is that OR returns 0 only if both bits are 0. We can think about the purpose of the OR gate as allowing us to set/turn on specific bits in a binary word. Here's an example:

  10 | 7

  00001010 = 10
| 00000111 = 7
-----------
  00001111

If you think about the second number (in this case 7) as being a set of instructions taken against the first number (10) we can see that by specifying 1's in specific columns, we can turn on or change the bits in the first number from 0 to 1, essentially turning on those bits. Again you could think of the user permissions example: by turning a single bit from off to on, a user could be upgraded to admin access for instance.

XOR (^)

The XOR or Exclusive-Or operator returns 1 only if both values are different, i.e. a 0 and a 1. Two ones or two zeros will return 0. If the AND operator can be used to read bits, and the OR operator can turn on bits, XOR allows us to toggle the state of specific bits.

   10 ^ 7

   00001010 
 ^ 00000111
------------
   00001101

Notice how anywhere there was a 1 in the second number, the original number's bit is toggled to be it's opposite.

NOT (~)

The NOT gate is the actual mechanism we can use in JavaScript to invert all of the values in order to compute the One's Complement of a binary word. NOT will invert every bit to be it's opposite.

00001010 = 10
11110101 = ~10

Left-Shift (<<)

The Left-Shift operator will shift all the bits in the first number to the left by the right number amount of positions. Each value that gets pushed into new columns on the left will be dropped, and each new position that is created on the right will be filled in with a zero. Here's an example

8 << 2

00001000 = 8
00100000 = 8 << 2 = 32

As you can see, the effect of a left-shift operation (x << y) is the same as multiplying x by 2 y times. One use of left-shift is that it allows us to perform carries in addition operations when the sum of a column is 2 or greater. Another application of this operator can be seen in working with RGB color values in Hexadecimal notation. We will see examples of these in later posts.

Right-Shift

There are two types of right-shift operations in JavaScript: Zero-Fill Right-Shift and Sign-Propagating Right-Shift. Zero-fill is used when dealing with unsigned numbers, and sign-propagating allows us to do the same right-shift operation with negative/signed numbers.

Zero-Fill Right-Shift (>>>)

Zero-fill right shift is used for positive or unsigned numbers. As each value is shifted right x number of positions, zeros are added to the left side of the number, and any values that get pushed further than the one column get dropped off.

10 >>> 2

00001010 = 10
00000010 = 10 >>> 2

Sign-Propagating Right Shift (>>)

Sign-Propagating allows us to right-shift negative or signed numbers. As the number is shifted, the values on the left will be filled in with the value of the signed bit, thus preserving the sign of the original number.

   -10 >> 2

   10001010 = -10
>> 11100010 = -10 >> 2 = -3?

Conclusion

Bitwise Operators allow us to manipulate bits on a granular level we cannot access with regular math operations. In the next post we will see some examples using Bitmasks and Hexadecimal notation...

Representing Negative Numbers in Binary Notation

Andrew Lederman — Fri, 10 Mar 2023 21:08:26 +0000

We've seen how to add two positive integers together in binary notation. But what happens when we try to subtract?

 0110
-0011
------
010(-1)???

You'll see pretty quickly that we can't subtract 1 from 0 in any given column, so we need a different way to handle subtraction operations in binary notation. There are technically 3 different ways that negative numbers can be represented in binary. The most common is called Two's Complement. But before we get to it, there are two other methods we need to know about...

1.Signed Magnitude

In Base 10, we can represent whether a number is positive or negative by adding the corresponding sign to the left of the number, as in +50 and -45. But we don't have a way to represent the sign directly in binary, we only have bits to work with. Signed means adding the sign (+ or -) to the number, and Magnitude is a term which refers to the actual value of the number. So in the number -65, '-' is the sign, and 65 is the magnitude of the number.

Binary numbers can be signed or unsigned. In a signed number, the left most bit is reserved to represent a positive or negative sign. A 0 in this column represents a positive sign (+) and a 1 represents the negative sign (-). In unsigned, the left most bit simply represents the number in that column. Unsigned numbers can only represent positive numbers and zero. Signed magnitude allows us to represent negative numbers in binary, so this is what we will use for the rest of this post.

10000001 = (-)1 signed
10000001 = 129 unsigned

MSB and LSB

We have seen how the left-most bit of a binary number can be reserved to represent a positive or negative sign. There is actual terminology that describes this position: Most Significant Bit (or MSB for short) describes the left most bit in a binary number. This is useful for describing the signed bit of a signed binary number. The Least Significant Bit (or LSB) describes the right most bit in a number, the ones position. You will come across these terms frequently as you work more with binary numbers.

2. One's Complement

We may be able to represent a sign, but we still aren't able to do an actual subtraction operation. To do this in binary, we need to change our thinking a bit. Instead of subtracting a number, we will add a negative number to the positive. In binary this requires some conversion of the subtrahend (number being subtracted) to make it work.

One's complement simply means to take all the bits of a number, and flip them. If the bit was 0, make it a 1. If it was 1, make it a 0.

0011 = 3
1100 = one's complement of 3

Now we can use this one's complement as the value we will add to our initial number. Let's say we want to subtract 3 from 7. We know that one's complement of 3 in binary is 1100. So we will add this to the binary representation of 7 which is 0111.

  0111 = 7
+ 1100 = one's complement of 3
-------
 10011 = 3?

You can see we are one short of the correct answer which is 4, and our result is currently negative. In One's complement computations if there is a carry bit in the MSB, we do a carry-around by taking the MSB and adding it to the LSB. This will give us the correct answer which is 0100 = 4.

It's important to note that the one's complement of a number is NOT the negative of that number. For instance the one's complement of 3 is 1100, which in binary actually represents the number +4. The complement is just that, a complementary value that when added to our minuend (number to be subtracted from) has the affect of giving us the correct result of a subtraction operation.

One's complement is a method for subtraction which is rarely used in actual computers these days, it is generally used in older systems. It has a shortcoming which is that it has two different representations for zero, positive and negative zero.

0000 = (+)zero
1111 = (-)zero (One's Complement of +zero)

Instead it is most common to see...

3. Two's Complement

Two's Complement is just One's Complement plus one! The only difference is instead of adding 1 after the computation, in Two's Complement we add 1 to our complement before we compute the sum. This is the most common form that a complement will take in binary systems.

Let's subtract 10 from 23 in binary. First we must convert the number to be subtracted into it's Two's Complement:

00001010 = 10 in binary

11110101 = One's Complement of 10

11110110 = Two's Complement of 10

First we take the One's Complement of 10 by flipping each bit in the number, then we add 1 to the LSB to get our Two's Complement. Now we are ready for our subtraction operation.

 00010111 = 23
+11110110 = 10
----------
100001101 = 13

Since we add the one before the operation, the result is the correct number! In Two's Complement, if our calculation has a carry in the MSB we can truncate it. Our final result is 13.

Conclusion

We've seen how to use Two's Complement to run subtraction operations on two binary numbers. In the next post we will learn about Bitwise Operators, which are a set of operations which gives us a lot more flexibility and greater manipulation of binary numbers!

Intro to Binary Numbers

Andrew Lederman — Tue, 07 Mar 2023 17:03:08 +0000

This is the beginning of a series on Binary Numbers and Bitwise Operators which will culminate in solving the 5 recommended Binary Algorithm Challenges from the LeetCode Blind 75.

What are Binary Numbers?

Binary is a method which computers use to represent numbers and data. You have probably heard of "zeros and ones". These are called 'bits' of data and they exist on a much lower level (i.e. closer to the hardware) than the higher-level programming languages the average developer works with such as Python or JavaScript.

Binary numbers can be measured in different units:

Bit: A bit is the smallest unit in binary, it represents one single value, either 0 or 1.
Nibble: A nibble is 4 bits!
Byte: A byte is 8 bits. From this we can infer the meaning of other units such as mega, kilo, giga, tera, and petabytes...

Binary numbers exist ultimately on a hardware level, specifically electronic circuitry! I am no electrical engineer, but a simple understanding of what happens on a computer chip has helped me to understand what binary is all about.

The Transistor

The transistor is considered one of the most important inventions of the 20th century. Transistors used to look something like this:

but now they look more like this:

and billions of them can exist on a single computer chip. An electric current will flow through them, and each has only two states, on or off, zero or one. This may remind you of boolean values in high-level programming languages, and you would be right to make this connection! On/Off, True/False, and 0/1 are all valid ways to think about transistors and binary in general.

When we write code we are essentially manipulating the computer chip at a hardware level, and building electronic circuits with transistors which will carry out our logical tasks. But I digress...

Base 10

Ok, so let's talk about numbers. The numbers we use every day are generally in what is called Base 10. In Base 10, each column of the number represents a certain multiple of ten. For instance, the right most digit always represents a number of 1s, up to the number 10. The 2nd column from the right represents 10's, so if you had a 3 in this column for instance, it would mean that there are 3 10's in this number. Here's an example:

1000 | 100 | 10 | 1 |
1       5     3   2 = 1,532

Base 2

Binary numbers are represented in Base 2. In Base 2, each column of the number represents a multiple of 2, remembering that the only values we have to work with are 0 and 1. So each column in base 2 can only be a zero or a one. That looks something like this:

128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
 0     0   1     1   0   1   0   1
= 00110101 in binary = 53 in base 10

Just add up the values at each column to determine what the number is in binary! This binary number has 1 in the 32 column, 1 in the 16 column, 1 in the 4 column, and 1 in the 1 column, which makes this number 32 + 16 + 4 + 1 = 53.

Adding numbers in Base 10

We should be familiar with adding two numbers together in Base 10. Lets add 63 and 58.

 63
+58
---
121

When the two numbers in one column add up to 10 or more, a one is carried over to the next column to the left. We add up each column from right to left until we have added both numbers together.

Adding numbers in Base 2

In Base 2 or Binary, we add numbers in a similar way. The only difference is if the value of the two digits added equals 2 or more, than we carry a 1 over to the next column. Let's see this in action:

 00110 = 6
+11011 = 27
------
100001 = 33

Try this yourself and you will see that any time you add 1 + 1 in a column, the result in that column will be 0, and a 1 will carry over one column to the left. In this case, there will be a carry in every column until we finally add a 16's column at the end of the addition in the left-most position.

Conclusion

Adding two positive numbers together in binary is fairly simple, but what if we want to subtract two numbers? This is not as straight forward in binary and requires a trick called Two's Complement which we will look at in the next post...