Bit manipulation: Difference between revisions

Revision as of 22:11, 13 November 2019

Revision as of 10:02, 21 February 2020

Line 1:

{{Short description|algorithmically modifying data below the word level}}

{{Use American English|date = March 2019}}

{{unreferencedrefimprove|date=AprilFebruary 20172020}}

'''Bit manipulation''' is the act of [[algorithm]]ically manipulating [[bit]]s or other pieces of [[Data (computing)|data]] shorter than a [[Word (data type)|word]]. [[Computer programming]] tasks that require bit manipulation include low-level device control, [[error detection]] and [[error correction|correction]] algorithms, [[data compression]], [[encryption]] algorithms, and [[Optimization (computer science)|optimization]]. For most other tasks, modern [[programming language]]s allow the [[programmer]] to work directly with [[Abstraction (computer science)|abstractions]] instead of bits that represent those abstractions. [[Source code]] that does bit manipulation makes use of the [[bitwise operation]]s: AND, OR, XOR, NOT, and possibly other operations analogous to the boolean operators; there are also [[bitwise operation#Bit shifts|bit 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.

Line 45:

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.). 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 is ''count leading zeros'' used to find the high set bit of a machine word, though it may have different names on various architectures<ref>On most Intel chips, it's BSR (bitscan reverse), though newer SoCs also have LZCNT (count leading zeros)</ref>. There's no simple programming language idiom, so it must be provided by a compiler intrinsic or system library routine. Without that operator, it is ''very'' expensive (see [[Find 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 1980's1980s. An accompanying operation ''count ones'', also called POPCOUNT, 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: