What are the techniques for java bit operations?

What is bit operation

We all know that the form of data stored in computers is binary data. Bit operation is a method of operating data at the binary level. Bit operation Directly operate on binary data composed of 0 and 1.

Basic bit operations

There are six basic bit operations, namely** AND or NOT XOR shift left and right**

## When both bits # and are 1, the result is 1. or when both bits are 0, the result is 1. 0^XORWhen the two bits are the same, the result is 1, if they are not the same, the result is 0 ~Inversion0 becomes 1, 1 becomes 0##>>

• ** First of all, it must be clear that bit operations can only operate on integers**

• In jdk, java right shift is an arithmetic right shift operation

• ** Bit operations have low priority, so it is best to use parentheses **

The output result of the above code:

Let’s analyze why this result is output:

• First of all, for 13 , we write its binary: 0000 1101

• Shift right by two places: 0000 0011. Since the right shift in jdk is an arithmetic right shift, the high bits are filled with 00, and the result is 3

• For -13, binary code: 1111 0011

• Shift right by two bits, high-order complement sign bit, 1111 1100, the result is -4

Commonly used bit operationsTips

Bit operations are often used for some small operations, because they can only operate on integers. numbers, so its uses are limited, but some commonly used tips are worth mastering, such as judging odd and even, exchanging two numbers, exchanging signs, finding absolute values, etc. We will introduce them one by one below.

Judge parity

The difference between parity and evenness is reflected in binary, that is, the end is 0, 1. Obviously, when the end is 0, it is an even number, and when the end is 1, it is the last One odd number. So the way to determine parity is:

A small test program:

The above program will output all Even numbers within 1000

Exchanging two numbers

The advantage of using bit operations to exchange two numbers is that there is no need for a third temp variable (the limitation is that only integer variables can be exchanged)

Analyze how the exchange occurs:
First a^=b, that is, a=(a^b);
b^=a, that is, b= b^(ab), since the ^{operation satisfies the commutative law, b}(a^b)=bb^a. A number that is XORed with itself must be 0, because it must be equal to itself. So if a number is XORed with 0, 1 and 0 will still be 1, and 0 and 0 will still be 0, so obviously a number and 0 After XOR, of course it is still itself. So at this time, b is assigned the value a.
The last step, a^=b is a=a^{b. Since the previous two steps show that a=(a}b), b=a, so a=a^{b means a=(a} b)^a. Therefore, a will be assigned the value of b.

Converting symbols

Converting symbols is obviously very simple. According to the similar complement code, just take the inverse and add one.

Finding the absolute value

Finding the absolute value is achieved on the basis of changing the sign. We only need to first determine whether it is a negative number. , if it is a negative number, change the sign, if not, just return it directly.
To determine the positive or negative, you can directly determine the sign bit, shift 31 bits to the right, get the sign bit, and determine the positive or negative

##For any number, XOR with 0 will Remaining unchanged, XOR with -1, which is 0xFFFFFFFF, is equivalent to negation. Therefore, the absolute value can also be obtained by XORing a with i and then subtracting i (because i is 0 or -1, so subtracting i means either adding 0 or adding 1). Therefore, the above code can be optimized:

Application of bit operations

Common algorithm problems, implementation of bit operations The operation of A and B is a common algorithm problem.

#The above code realizes the addition operation of two numbers without using operators and using bit operations.

Now let’s explain the principle of bit operation to add two numbers
First of all, in decimal, we know that, 7 8, the sum without carry is 5, the carry is 1, and then we can use the sum without carry and carry 5 1*10 calculates the final result 15.
This method can also be adopted for similar binary systems
For example,
a = 3, b = 6
a: 0011
b: 0110
Without carry sum: 0101, which is 5
Carry: 0010 which is 2
so a b becomes 5 (25　 0101
2No carry and 0001 = 1
Carry 0100 = 4
Therefore a b becomes 1 4 and then there is
1　 0001
4 without carry and 1001 = 9
with carry 0000 = 0
When the carry is 0, the sum without carry is 9, which is the sum of a and b.

You can find that the above is a recursive process, so it is not difficult to write the code. Finding the carry-free sum of two numbers is actually just an XOR operation of the two numbers.

Symbol	Description	Operation rules
&
Shift left	Each binary bit is shifted to the left by a certain number of bits, the high bit is discarded, and the low bit is filled with 0
Shift right	Each binary bit is shifted to the left by a certain number of bits, the high bit is discarded, and the high bit is filled with the sign bit or zero, depending on the compiler

The above is the detailed content of What are the techniques for java bit operations?. For more information, please follow other related articles on the PHP Chinese website!