Bitwise operation

It is a fast and simple action, basic to the higher-level arithmetic operations and directly supported by the processor.

Most bitwise operations are presented as two-operand instructions where the result replaces one of the input operands.

While modern processors usually perform addition and multiplication just as fast as bitwise operations due to their longer instruction pipelines and other architectural design choices, bitwise operations do commonly use less power because of the reduced use of resources.

[1] In the explanations below, any indication of a bit's position is counted from the right (least significant) side, advancing left.

A simple but illustrative example use is to invert a grayscale image where each pixel is stored as an unsigned integer.

This technique is an efficient way to store a number of Boolean values using as little memory as possible.

For example: The bitwise XOR may be used to invert selected bits in a register (also called toggle or flip).

Assembly language programmers and optimizing compilers sometimes use XOR as a short-cut to setting the value of a register to zero.

If the set of bit strings of fixed length n (i.e. machine words) is thought of as an n-dimensional vector space

If the width of the register (frequently 32 or even 64) is larger than the number of bits (usually 8) of the smallest addressable unit, frequently called byte, the shift operations induce an addressing scheme from the bytes to the bits.

In the second case, the rightmost 1 was shifted out (perhaps into the carry flag), and a new 1 was copied into the leftmost position, preserving the sign of the number.

If the binary number is treated as ones' complement, then the same right-shift operation results in division by 2n and rounding toward zero.

Rotate through carry is especially useful when performing shifts on numbers larger than the processor's native word size, because if a large number is stored in two registers, the bit that is shifted off one end of the first register must come in at the other end of the second.

The result of shifting by a bit count greater than or equal to the word's size is undefined behavior in C and C++.

Care must be taken to ensure the statement is well formed to avoid undefined behavior and timing attacks in software with security requirements.

[6] For example, a naive implementation that left-rotates a 32-bit unsigned value x by n positions is simply However, a shift by 0 bits results in undefined behavior in the right-hand expression (x >> (32 - n)) because 32 - 0 is 32, and 32 is outside the range 0–31 inclusive.

However, the branch adds an additional code path and presents an opportunity for timing analysis and attack, which is often not acceptable in high-integrity software.

Clang provides some rotate intrinsics for Microsoft compatibility that suffers the problems above.

For example, the following assigns x the result of shifting y to the left by two bits: Bitwise operations are necessary particularly in lower-level programming such as device drivers, low-level graphics, communications protocol packet assembly, and decoding.

[13] For example, here is a pseudocode implementation of ancient Egyptian multiplication showing how to multiply two arbitrary integers a and b (a greater than b) using only bitshifts and addition: Another example is a pseudocode implementation of addition, showing how to calculate a sum of two integers a and b using bitwise operators and zero-testing: Sometimes it is useful to simplify complex expressions made up of bitwise operations, for example when writing compilers.

The goal of a compiler is to translate a high-level programming language into the most efficient machine code possible.

Operations without inverses lose some of the original data bits when they are performed, and it is not possible to recover this missing information.