 | This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Bit manipulation" – news ·newspapers ·books ·scholar ·JSTOR(February 2020) (Learn how and when to remove this message) |
Bit manipulation is the act ofalgorithmically manipulatingbits or other pieces ofdata shorter than aword.Computer programming tasks that require bit manipulation include low-level device control,error detection andcorrection algorithms,data compression,encryption algorithms, andoptimization. For most other tasks, modernprogramming languages allow theprogrammer to work directly withabstractions instead of bits that represent those abstractions.
Source code that does bit manipulation makes use of thebitwise operations: AND, OR, XOR, NOT, and possibly other operations analogous to the Boolean operators; there are alsobit shifts and operations to count ones and zeros, find high and low one or zero, set, reset and test bits, extract and insert fields, mask and zero fields, gather and scatter bits to and from specified bit positions or fields.Integer arithmetic operators can also effect bit-operations in conjunction with the other operators.
Bit manipulation, in some cases, can obviate or reduce the need to loop over a data structure and can give manyfold speed-ups, as bit manipulations are processed in parallel. However if the operation is unusual or costly toimplement its inclusion cannot be justified, inspiring innovative research.[1]
Bit twiddling,bit fiddling,bit bashing, andbit gymnastics are often used interchangeably with bit manipulation, but sometimes exclusively refer to clever or non-obvious ways or uses of bit manipulation, or tedious or challenginglow-level device control data manipulation tasks, for which the more accurate colloquial term is known asbit banging.
The termbit twiddling dates fromearly computing hardware, where computer operators would make adjustments by tweaking ortwiddling computer controls. As computer programming languages evolved, programmers adopted the term to mean any handling of data that involved bit-levelcomputation.
A bitwise operation operates on one or morebit patterns orbinary numerals at the level of their individualbits. It is a fast, primitive action directly supported by thecentral processing unit (CPU), and is used to manipulate values for comparisons and calculations.
On most processors, the majority of bitwise operations are single cycle - substantially faster than division and multiplication and branches. While modern processors usually perform some arithmetic and logical operations just as fast as bitwise operations due to their longerinstruction pipelines and otherarchitectural design choices, bitwise operations do commonly use less power because of the reduced use of resources.
To determine if a number is a power of two, conceptually we may repeatedly do integer divide by two until the number won't divide by 2 evenly; if the only factor left is 1, the original number was a power of 2. Using bit and logical operators, there is a simple expression which will return true (1) or false (0):
boolisPowerOfTwo=(x!=0)&&((x&(x-1))==0);
The second half uses the fact that powers of two have one and only one bit set in their binary representation:
x == 0...010...0x-1 == 0...001...1x & (x-1) == 0...000...0If the number is neither zero nor a power of two, it will have '1' in more than one place:
x == 0...1...010...0x-1 == 0...1...001...1x & (x-1) == 0...1...000...0
If inlineassembly language code is used, then an instruction (popcnt) that counts the number of 1's or 0's in the operand might be available; an operand with exactly one '1' bit is a power of 2. However, such an instruction may have greater latency than the bitwise method above.
Processors typically provide only a subset of the useful bit operators. Programming languages don't directly support most bit operations, so idioms must be used to code them. The 'C' programming language, for example provides only bit-wise AND(&), OR(|), XOR(^) and NOT(~). Fortran provides AND(.and.), OR (.or.), XOR (.neqv.) and EQV(.eqv.). When the full set ofbitwise operators are provided they areBoolean functions of either two or three operands.
Algol provides syntactic bitfield extract and insert. When languages provide bit operations that don't directly map to hardware instructions, compilers must synthesize the operation from available operators.
An especially useful bit operation iscount leading zeros used to find the high set bit of a machine word, though it may have different names on various architectures.[2] There's no simple programming language idiom, so it must be provided by a compiler intrinsic or system library routine. Without that operator, it isvery expensive (seeFind first set#CLZ) to do any operations with regard to the high bit of a word, due to the asymmetric carry-propagate of arithmetic operations. Fortunately, most cpu architectures have provided that since the middle 1980s. An accompanying operationcount ones, also calledPopcount, which counts the number of set bits in a machine word, is also usually provided as a hardware operator.
Simpler bit operations like bit set, reset, test and toggle are often provided as hardware operators, but are easily simulated if they aren't - for example (SET R0, 1; LSHFT R0, i; OR x, R0) sets bit i in operand x.
Some of the more useful and complex bit operations that must be coded as idioms in the programming language and synthesized by compilers include:
Some arithmetic operations can be reduced to simpler operations and bit operations:
Multiply by 9 for example, is copy operand, shift up by 3 (multiply by 8), and add to original operand.
Bit-reversing, byte-reversing, and the various forms of rotation, can all be costly in terms of the number of instructions needed. Shifting has variants including Arithmetic shift, Logical shift and Rotate.
Unusual instructions includePacked BCD which are very common in the financial, commercial and industrial industries.
A mask is data that is used forbitwise operations, particularly in abit field.
Using a mask, multiple bits in aByte,nibble,word (etc.) can be set either on, off or inverted from on to off (or vice versa) in a single bitwise operation. More comprehensive applications of masking, when applied conditionally to operations, are termedpredication.