Source code, inverse code and complement review

All the computer needs to keep for a number is its binary form. But what about signed numbers? Source code, inverse code, complement code is the machine store a signed number specific encoding.

The original code

The source code is the sign bit plus the absolute value of the value, that is, the first bit represents the symbol and the remaining bits represent the value. For example, if it is 8-bit binary plus and minus 1:

[+1] = [0000 0001] Original [-1] = [1000 0001] original

Radix-minus-one complement

The inverse code is expressed as follows:

• The inverse of a positive number is itself;
• The inverse of a negative number is based on its original code, the sign bit is unchanged, the rest of the bits are inverse.

[+1] = [0000 0001] = [0000 0001

[-1] = [1000 0001] = [1111 1110

complement

The expression of complement is as follows:

• The complement of a positive number is itself;
• The complement of a negative number is based on its original code, the sign bits remain unchanged, the other bits are reversed, and then +1. (i.e., inverse plus 1);

As you can see, the positive numbers are the same regardless of the encoding; Inverse and complement are mainly used to deal with negative numbers. In computer system, complement code is generally used to represent signed numbers. The benefits of using the complement are:

• The symbol problem of 0 and two coding problems of 0 are solved.
• Sign bit and number range can be unified processing, addition and subtraction can also be unified processing
• The operation process of complement code and source code conversion is the same, no extra hardware circuit is needed;

An operator

Bitwise operations operate directly on the binary bits of an integer in memory. Compared with ordinary integer arithmetic operations, bit operations are low-level operations, which are more efficient and simpler in code. The bit operations supported in Java are:

• &: the bitwise and

If both corresponding bits are 1, the result is 1; otherwise, it is 0

• |: or by location

If both corresponding bits are 0, the result is 0; otherwise, it is 1

• ~: not by location

The bitwise inverse operator flips each bit of the operand, that is, 0 becomes 1, and 1 becomes 0

• ^: XOR by bit

The result is 0 if the corresponding bit values are the same, 1 otherwise

• <<: left shift operator

The left operand moves the right operand by bits to the left

• >>: right shift operator

The left operand moves right by bit to the number of digits specified by the right operand

• >>>: unsigned right shift operator

The value of the left-hand operand moves to the right by the number of digits specified by the right-hand operand, and the resulting space is filled with zeros

The title

Given an integer n, determine whether the integer is a power of 2. If so, return true; Otherwise, return false. If there is an integer x such that n == 2x, n is considered to be a power of 2.

Source: LeetCode

Link: leetcode-cn.com/problems/po… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

The sample

code

package com.vleus.algorithm.bit_operator;

/ * * *@author vleus
 * @date08:02, 2021 23:04 */
public class PowerOfTwo {

    // Method 1: Divide by 2 to determine the remainder
    public boolean isPowerOfTwo(int n) {

        if (n <= 0) {
            return false;
        }

        // Keep dividing by 2 until the result is odd
        while (n % 2= =0) {
            n = n / 2;
        }

        // If n eventually becomes 1, it is 2 to the full power
        return n==1;
    }

    // Method two: bit operation: with its own -1 do bit sum, binary number and its -1 digit sum must be 0
    public boolean isPowerOfTow2(int n) {

        if (n <= 0) {
            return false;
        }

        return (n & n - 1) = =0;
    }

    // Method three: bit operation: with its own -1 do bit sum, binary number and its -1 digit sum must be 0
    public boolean isPowerOfTow3(int n) {

        if (n <= 0) {
            return false;
        }

        return(n & -n) == n; }}Copy the code