The number of ones in binary

preface

If you have an integer, and you want to know that its binary representation has more than one, what do you do? This article will take you to in-depth study binary and its various operations, step by step to study the solution to this problem, welcome interested developers to read this article.

Front knowledge

Before we can solve this problem, we need to understand what binary is.

binary

In the computer world, there are only zeros and ones, or binary.

Number of symbols

In binary, numbers are divided into signed and unsigned numbers.

For the signed number, the sign of the positive and negative machine is unable to recognize, but because “positive” and “negative” are exactly two different states, if “0” is used to represent positive, “1” is used to represent “negative”, so the symbol is digitized, and it is stipulated to put it in front of the significant number, that is, the signed number is formed.

Therefore, the highest bit is used to represent symbols in binary.

• The highest digit is 0, which is a positive number.
• The highest digit is 1, which is negative.

The highest bit of binary is the first bit, for example, 10000001100, which has the highest bit 1.

For unsigned numbers, the range of the numbers it represents is positive, and all bits are used to indicate the size of the number.

Having the property of a signed number

For signed numbers, it has six properties:

• The highest bit of binary is the sign bit: 0 represents a positive number and 1 represents a negative number
• Positive numbers have the same source code, inverse code, and complement
• The inverse of a negative number = the symbol bits of its source code remain unchanged, and the other bits are reversed (0 -> 1; 1 – > 0)
• The inverse and complement of 0 are 0
• The complement of a negative number = its inverse + 1
• In the computer operation, are in the way of complement to operate

Source code, inverse code, complement code

In the above properties, we have mentioned the original code, inverse code, complement code, next we will learn what they are.

• Source code, divided into two cases:
  • A positive number, a binary number converted to absolute value
  • A negative number, converted to a binary number in absolute value, followed by the highest complement of 1
• Inverse code, also divided into two cases:
  • A positive number whose inverse is the same as its source
  • A negative number whose inverse code is the source code of the number except the sign bits
• Complement, also divided into two cases:
  • A positive number whose complement is the same as its source
  • A negative number whose complement is the addition of 1 to the last digit of the source except the sign bit

Hexadecimal conversion

We need to convert a decimal number to binary before we do binary operations, so we need to learn how to convert a decimal number to binary.

Decimal to binary

There are three main cases for converting decimal to binary:

• A positive integer is converted to binary

The calculation rule is: mod two (until the quotient is 0), and then reverse order, high zero.

Now that we know the rules, as an example, let’s find the binary number for 80, as shown below:

The unit of bytes used internally to represent numbers is a fixed length (word length), such as 8, 16, 32, 64 bits. Therefore, when the number of bits calculated in binary is not enough, it is necessary to supplement 0 in high order.

In the example above, we convert 80 to binary and the value is 1010000 and the word length is 7. If the computer’s word length is 64 bits, the standard way to write it is to add 57 zeros in front of the highest bit, as shown in the calculator:

• Negative integer to binary

In the computer, the negative number is expressed in the form of the complement of the original code. Through previous learning, we know that if we want to find the complement of the negative number, we have to find its original code first.

Let’s take -80 as an example to calculate its binary code. The steps are as follows:

1. Find the original code, as shown below:

2. Find the complement, as shown below:

At this point, we have the binary code for -80:10110000

In the conversion from positive integer to binary section, we explained that computers are fixed word lengths, and when the number of binary digits calculated is insufficient, positive integers will be supplemented with zeros at the highest level, and negative integers will be supplemented with ones at the highest level.

Let’s use our calculator to verify that our -80 binary code is correct, as shown below:

• Decimal to binary

In binary, decimals are called floating-point numbers, and when we convert a decimal decimal to a binary decimal, we need to split it into integer and decimal parts with the decimal point as the boundary.

The integer part is converted to binary, which we’ve already talked about.

To convert the decimal part to binary, multiply by 2 to take the whole part, and continue to multiply the decimal part by 2 until the decimal part is 0 (in most cases it will not be 0, so you need to establish accuracy).

Let’s take 80.13 as an example to calculate its binary code, as shown below:

Most decimal decimals cannot be expressed exactly in binary, depending on the computer’s word length.

In the figure above, we calculate the binary code for 80.13 to be 01010000.00100, and we are accurate to five decimal places.

Let’s use our calculator to see if we’re right.

Binary to decimal

Similarly, there are three cases of binary to decimal conversion:

• A positive integer is converted to decimal

Starting with the lowest digit of the binary, number each digit, take the ordinal number of the non-zero digit, compute it as a power of two, and add the results.

Let’s take 01010000 as an example to find its decimal number, as shown below:

• The negative integer is converted to decimal

Before we learned the decimal negative integer to binary method, so binary to decimal, need to calculate backwards, we take 10110000 as an example, the steps are as follows:

1. Find the source code according to the complement

2. Remove the sign bit, calculate the other bits according to the rule of converting positive integer to binary, and finally fill in the negative sign, as shown in the figure below:

• Decimal to decimal

Place a negative number (starting at -1) on each digit after the decimal point, take the number in the non-zero position, compute it as a power of 2, and add the results.

Let’s take 01010000.00100 as an example to calculate its decimal number, as shown in the figure below:

After the previous learning, we know that decimal decimal to binary, in most cases is not accurate value, we use 80.13 example, accurate to 5 decimal places.

Similarly, when we convert a binary decimal to a decimal number, we can’t get the exact value. The final value depends on the precision, so we keep two decimal places and round them to 80.13.

Operation of signed numbers

So with that out of the way, let’s do a couple of examples of how signed numbers work.

Left shift operator

<< is called the left shift operator, and it operates as follows:

• Removes the highest bit of binary 0
• Add a 0 to the end of the binary number

Let’s take 01010000 as an example, assuming that its word length is 32 bits (the redundant 0 is omitted), move it one bit to the left, and its operation process is shown in the following figure:

Moving one bit to the left gives us 010100000, which in decimal is 2^5 + 2^7 = 32 + 128 = 160.

The decimal number of 01010000 is 80. After moving one bit to the left, the value becomes 160. After observation, we find that the left value is exactly twice the original value, which is equivalent to multiplying by two.

Most of the time we can use this as a multiplied by two, but there are special cases where it doesn’t really represent a multiplied by two. For example, we need to move it 25 places to the left, as shown below (we fill in the missing zeros) :

When we move it 25 places to the left, we see that the 0 has been removed, the highest digit has become a 1, and this number has gone from being positive to negative. If we move 26 places to the left, we don’t have enough zeros on the left, we start evaluating from the right, and we end up with a positive number again.

Therefore, we can find the following rule:

• When the left shift exceeds the remaining word length, its value is not multiplied by two

Note: If any binary number moves the number of bits to the left more than or equal to the word length (for example, if the word length is 32, we move 32 bits to the left and add 32 zeros to the right), then the corresponding decimal number will be 0.

Of course not. When a binary number moves to the left, when the number of bits moved is greater than or equal to its word length, the digit moves to the left after the remainder.

For example, if we need to shift a 32-bit binary number 32 bits to the left, we need to find its remainder first, i.e. : 32% 32 = 0, we need to shift 0 bits to the left. Moving 33 bits to the left is the same as moving 1 bit to the left.

Right shift operator

>> is called the right shift operator, and its operation rules are divided into positive and negative cases.

Positive:

Remove the lowest digit and fill in the highest digit with a 0.

Take 01010000 as an example (the decimal value is 80) and move it 4 bits to the right, as shown in the figure below:

The calculated binary result is 00101, transposed to decimal, and the result is: 2^0 + 2^2 = 1 + 4 = 5, i.e. : 80 >> 4 = 5

Let’s verify this with a calculator:

Negative:

After previous learning, we know that negative numbers are stored in the form of the complement of the original code, and its right shift rule is:

• Shift the complement to the right and fill in the highest bit with 1
• Find its inverse
• For the inverse +1, find the original code

Let’s take 10110000 as an example (-80 in decimal) and move it 4 bits to the right as follows:

The calculated binary result is 11100, which we make special decimal: 2^0 + 2^2 = 1 + 4 = 5, complete with sign bits, resulting in: -5. That is, -80 >> 4 = -1.

Let’s use a calculator to verify this, as shown below:

And the operator.

& is called the and operator, which operates as follows:

• If both sides of the symbol are 1, the result is 1; otherwise, 0

That is: 0 & 0 = 0; 0 & 1 = 0; 1 & 0 = 0; 1 & 1 = 1

Let’s look at a decimal example and see how it works, as follows:

15 & 13, its operation steps are:

• Convert decimal to binary
• And on binary

The operation process is shown in the figure below:

Or operator.

| called or operator, operation rules of it are as follows:

• If one of the numbers on the left and right of the sign is 1, the value is 1

Namely: 0 | 1 = 1; 1 | 0 = 1; 0 | 0 = 0; 1 | = 1

Before we continue the chapter number, for example, look at 13 of 15 | operation steps:

• Convert decimal to binary
• To operate or on binary

The operation process is shown in the figure below:

Xor operator

^ Called the xOR operator, it operates as follows:

• The number on the left and right sides of the symbol, with different values, is 1, otherwise 0

Namely: 0 ^ 0 = 0; 0 ^ 1 = 1; 1 ^ 0 = 1; 1 ^ 1 = 0

Using 15 and 13 as examples, let’s look at the operation steps of 15^13:

• Convert decimal to binary
• Xor operation on binary

The operation process is shown in the figure below:

Problem solving

With that in mind, let’s get down to business: if you have a decimal integer, find the number of ones in its binary number.

Analysis of the

Before we solve this problem, let’s analyze a scenario like this:

If an integer is not equal to 0, then at least one of the binary representations of the integer is 1.

Let’s assume that the rightmost digit of this number is 1, so when we subtract 1, the last digit becomes 0 and everything else stays the same. So the last digit is kind of the reverse operation, going from a 1 to a 0.

Next, assume that the rightmost digit of the number is 0:

If the rightmost 1 in the binary representation of the integer is in the MTH bit, then subtracting 1:

• The MTH bit goes from 1 to 0

• Every 0 after the MTH bit becomes a 1

• All bits of the integer up to the MTH bit remain the same

Let’s take an example:

A binary number 01010000, whose fourth bit is the first 1 from the lowest digit, subtracted by 1:

• The fourth bit goes to 0
• All four zeros after it become ones
• All the bits in front of it stay the same

So the result is 01001111, or 79 in decimal.

conclusion

In both cases, we found that subtracting 1 from an integer turns the rightmost 1 into a 0. If it has a 0 to the far right, then all the zeros become ones, and all the bits to its left remain the same.

Next, we take the sum of an integer and subtract 1 from it, which is equivalent to making its rightmost 1 0. Let’s take the example of 01010000, which is 01001111 minus 1. We then carry out bitwise and operation on both of them, and the result is: 01000000.

After observation, we find: change the 1 on the right of 01010000 to 0, and the result is 01000000.

Ideas and Coding

See here, I think the developers already see the solution to this problem 🤓.

That’s right, the idea is that subtracting 1 from an integer and doing a bit sum with the original integer will turn the rightmost 1 of the integer into a 0.

So, how many 1’s there are in the binary representation of an integer, how many times can we do this operation until the whole number is zero, and we count each operation to get the answer to this question.

With this in mind, we can happily code as follows:

export default class BinaryOperation {
  /** * Get the number of 1's in binary *@param DecimalVal Decimal number */
  public getBinaryOneNum(decimalVal: number) :number {
    let count = 0;
    // If a decimal number is not 0, 1 still exists in its binary representation
    while(decimalVal ! = =0) {
      // The total number of 1s in binary +1
      count++;
      // Performs the bit-sum operation on a decimal number and the number after -1
      // After the result is obtained, replace the original decimal number and proceed to the next round of calculation until the decimal number is 0
      decimalVal = decimalVal & (decimalVal - 1);
    }
    // Return the result
    returncount; }}Copy the code

Finally, let’s write a test case to verify that the above code works, as follows:

import BinaryOperation from ".. /BinaryOperation.ts";

const binaryOperation = new BinaryOperation();
const result = binaryOperation.getBinaryOneNum(80);
const result2 = binaryOperation.getBinaryOneNum(-80);
console.log(The binary representation of '80${result}1 `);
console.log(In the binary representation of minus 80${result2}1 `);

Copy the code

The running results are as follows:

Example code addresses: binaryOperation. ts, binaryOperation-test.ts

The running result is consistent with the number of 1 in the binary number calculated manually 😋

-80 we figured out in the previous chapter that the binary representation is 10110000, and we said that the number of bits in the computer depends on the length of the word, and we only need to indicate the sign bit when we write, and we can omit the extra 1 in the high place.

Here, we calculate that there are 27 ones in the binary representation of -80. We add the five zeros here, and we know that its word length is 27 + 5 = 32.

Write in the last

At this point, the article is shared.

I’m an amazing programmer, a front-end developer.

If you are interested in me, please visit my personal website for further information.

• If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
• This article was first published in nuggets. Reprint is prohibited without permission 💌