Bit manipulation: Difference between revisions

Revision as of 06:03, 10 August 2025

Latest revision as of 13:52, 15 August 2025

(2 intermediate revisions by the same user not shown)

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

Line 45 ⟶ 47:

{{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.). When the full set of [[Bitwise_operation#Bitwise_operators|bitwise operators]] are provided they are [[boolean 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 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.

Line 66 ⟶ 70:

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.