Bit manipulation: Difference between revisions

Revision as of 15:20, 22 October 2021

Latest revision as of 13:52, 15 August 2025

(28 intermediate revisions by 11 users not shown)

Line 1:

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

{{Other uses|Manipulation (disambiguation){{!}}Manipulation}}

{{Distinguish|Bit-banging|Bit-banding|Byte grabber}}

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

{{refimprove|date=February 2020}}

'''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.

{{Confuse|Bit banging}}

'''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.

[[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.

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 many-foldmanyfold speed -ups, as bit manipulations are processed in parallel. However if the operation is unusual or costly to [[Instruction_set_architecture#Instruction_set_implementation|implement]] its inclusion cannot be justified, inspiring innovative research.<ref>https://www.researchgate.net/publication/4217315_Performance_and_energy_benefits_of_instruction_set_extensions_in_an_FPGA_soft_core</ref>

== Terminology ==

''Bit twiddling'', and''bit fiddling'', ''bit bashing'', and ''bit 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 challenging [[High- and low-level|low-level]] device control data manipulation tasks, for which the more accurate colloquial term is known as [[bit banging]].

The term ''bit twiddling'' dates from [[History of computing hardware|early computing hardware]], where computer operators would make adjustments by tweaking or ''twiddling'' computer controls. As computer programming languages evolved, programmers adopted the term to mean any handling of data that involved bit-level [[computation]].

== Bitwise operation ==

{{main|bitwiseBitwise operation}}

A bitwise operation operates on one or more [[bit pattern]]s or [[Binary numeral system|binary numerals]] at the level of their individual [[bit]]s. It is a fast, primitive action directly supported by the [[central processing unit]] (CPU), and is used to manipulate values for comparisons and calculations.

Line 22 ⟶ 24:

== Example of bit manipulation ==

{{See also|SWAR#Examples}}

To determine if a number is a power of two, conceptually we may repeatedly do integer divide by two until the

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):

<syntaxhighlight lang="cpp">

bool isPowerOfTwo = (x != 0) && ((x & (x - 1)) == 0);

</syntaxhighlight>

The second methodhalf uses the fact that powers of two have one and only one bit set in their binary representation:

x == 0...0<span style="color:red">1</span>0...0

x-1 == 0...001...1

Line 39 ⟶ 42:

x & (x-1) == 0...<span style="color:red">1</span>...000...0

If inline [[assembly 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.

== Bit manipulation operations==

{{see also|Bit Manipulation Instruction Sets}}

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 languagesthe providefull bitset operationsof that[[Bitwise_operation#Bitwise_operators|bitwise don'toperators]] directlyare mapprovided tothey hardwareare instructions,[[boolean compilersfunctions]] mustof synthesizeeither thetwo operationor fromthree available operatorsoperands.

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 1980s. 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.

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 1980s. An accompanying operation ''count ones'', also called POPCOUNT[[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.

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:

Line 58 ⟶ 65:

*bitfield scatter/gather operations which distribute contiguous portions of a bitfield over a machine word, or gather disparate bitfields in the word into a contiguous portion of a bitfield (see recent Intel PEXT/PDEP operators). Used by cryptography and video encoding.

*matrix inversion

Some arithmetic operations can be reduced to simpler operations and bit operations:

* reduce multiply by constant to sequence of shift-add

Multiply by 9 for example, is copy operand, shift up by 3 (multiply by 8), and add to original operand.

* reduce division by constant to sequence of shift-subtract

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 include [[Binary-coded decimal#Packed BCD|Packed BCD]] which are very common in the financial, commercial and industrial industries.

=== Masking ===

{{main|maskMask (computing)}}

A mask is data that is used for [[bitwise operation]]s, particularly in a [[bit field]].

Line 70 ⟶ 82:

== See also ==

{{Cols|colwidth=40em}}

* {{Annotated link|Bitwise operation}}

* [[Bit array]]

* [[Bit banding]]

* [[Bit banging]]

* [[Bit field]]

* [[{{Annotated link|Bit manipulation instruction set]] — bit manipulation extensions for the [[x86]] instruction set.}}

* [[BIT predicate]]

* [[Bit specification (disambiguation)]]

* [[Bit twiddler (disambiguation)]]

* ''[[Hacker's Delight]]'' – book on fast bit-level and low-level arithmetic algorithms.

* [[Nibble]] — unit of data consisting of 4 bits, or half a byte

* [[Predication (computer architecture)]] where bit "masks" are used in [[Vector processors]]

* [[Single-event upset]]

* [[SIMD within a register]] (SWAR)

{{Colend}}

== References ==

Line 86 ⟶ 104:

== Further reading ==

* {{cite book |last=Warren |first=Henry S. |date=2013 |title=[[Hacker's Delight]] |edition=2nd |publisher=Addison–Wesley Professional |page=512 |isbn=978-0321842688}}

* {{cite book |last=Knuth |first=Donald E. |date=2009 |title=[[The Art of Computer Programming]] Volume 4, Fascicle 1: Bitwise tricks & techniques; Binary Decision Diagrams |edition=1st |publisher=Addison–Wesley Professional |page=272 |isbn=978-0321580504 }} ([http://www-cs-faculty.stanford.edu/~knuth/fasc1a.ps.gz Draft of Fascicle 1a] {{Webarchive|url=https://web.archive.org/web/20191016044101/http://www-cs-faculty.stanford.edu/~knuth/fasc1a.ps.gz |date=2019-10-16 }} available for download)

== External links ==