Bitwise operations in C

Last updated

In the C programming language, operations can be performed on a bit level using bitwise operators.

Contents

Bitwise operations are contrasted by byte-level operations which characterize the bitwise operators' logical counterparts, the AND, OR, NOT operators. Instead of performing on individual bits, byte-level operators perform on strings of eight bits (known as bytes) at a time. The reason for this is that a byte is normally the smallest unit of addressable memory (i.e. data with a unique memory address).

This applies to bitwise operators as well, which means that even though they operate on only one bit at a time they cannot accept anything smaller than a byte as their input.

All of these operators are also available in C++, and many C-family languages.

Bitwise operators

C provides six operators for bit manipulation. [1]

SymbolOperator
&bitwise AND
|bitwise inclusive OR
^bitwise XOR (exclusive OR)
<<left shift
>>right shift
~bitwise NOT (one's complement) (unary)

Bitwise AND &

bit abit ba & b (a AND b)
000
010
100
111

The bitwise AND operator is a single ampersand: &. It is just a representation of AND which does its work on the bits of the operands rather than the truth value of the operands. Bitwise binary AND performs logical conjunction (shown in the table above) of the bits in each position of a number in its binary form.

For instance, working with a byte (the char type):

     11001000      & 10111000       --------     = 10001000

The most significant bit of the first number is 1 and that of the second number is also 1 so the most significant bit of the result is 1; in the second most significant bit, the bit of second number is zero, so we have the result as 0. [2]

Bitwise OR |

bit abit ba | b (a OR b)
000
011
101
111

Similar to bitwise AND, bitwise OR performs logical disjunction at the bit level. Its result is a 1 if either of the bits is 1 and zero only when both bits are 0. Its symbol is | which can be called a pipe.

      11001000       | 10111000        --------      = 11111000

[2]

Bitwise XOR ^

bit abit ba ^ b (a XOR b)
000
011
101
110

The bitwise XOR (exclusive or) performs an exclusive disjunction, which is equivalent to adding two bits and discarding the carry. The result is zero only when we have two zeroes or two ones. [3] XOR can be used to toggle the bits between 1 and 0. Thus i = i ^ 1 when used in a loop toggles its values between 1 and 0. [4] 

      11001000       ^ 10111000        --------      = 01110000

Shift operators

There are two bitwise shift operators. They are

Right shift >>

The symbol of right shift operator is >>. For its operation, it requires two operands. It shifts each bit in its left operand to the right. The number following the operator decides the number of places the bits are shifted (i.e. the right operand). Thus by doing ch >> 3 all the bits will be shifted to the right by three places and so on.

However, do note that a shift operand value which is either a negative number or is greater than or equal to the total number of bits in this value results in undefined behavior. For example, when shifting a 32 bit unsigned integer, a shift amount of 32 or higher would be undefined.

Example:

If the variable ch contains the bit pattern 11100101, then ch >> 1 will produce the result 01110010, and ch >> 2 will produce 00111001.

Here blank spaces are generated simultaneously on the left when the bits are shifted to the right. When performed on an unsigned type or a non-negative value in a signed type, the operation performed is a logical shift, causing the blanks to be filled by 0s (zeros). When performed on a negative value in a signed type, the result is technically implementation-defined (compiler dependent), [5] however most compilers will perform an arithmetic shift, causing the blank to be filled with the set sign bit of the left operand.

Right shift can be used to divide a bit pattern by 2 as shown:

i=14;// Bit pattern 00001110j=i>>1;// here we have the bit pattern shifted by 1 thus we get 00000111 = 7 which is 14/2

Right shift operator usage

Typical usage of a right shift operator in C can be seen from the following code.

Example:

#include<stdio.h>voidshowbits(unsignedintx){inti=0;for(i=(sizeof(int)*8)-1;i>=0;i--){putchar(x&(1u<<i)?'1':'0');}printf("\n");}intmain(void){intj=5225;printf("%d in binary \t\t ",j);showbits(j);/* the loop for right shift operation */for(intm=0;m<=5;m++){intn=j>>m;printf("%d right shift %d gives ",j,m);showbits(n);}return0;}

The output of the above program will be

5225 in binary           00000000000000000001010001101001 5225 right shift 0 gives 00000000000000000001010001101001 5225 right shift 1 gives 00000000000000000000101000110100 5225 right shift 2 gives 00000000000000000000010100011010 5225 right shift 3 gives 00000000000000000000001010001101 5225 right shift 4 gives 00000000000000000000000101000110 5225 right shift 5 gives 00000000000000000000000010100011

Left shift <<

The symbol of left shift operator is <<. It shifts each bit in its left-hand operand to the left by the number of positions indicated by the right-hand operand. It works opposite to that of right shift operator. Thus by doing ch << 1 in the above example (11100101) we have 11001010. Blank spaces generated are filled up by zeroes as above.

However, do note that a shift operand value which is either a negative number or is greater than or equal to the total number of bits in this value results in undefined behavior. This is defined in the standard at ISO 9899:2011 6.5.7 Bit-wise shift operators. For example, when shifting a 32 bit unsigned integer, a shift amount of 32 or higher would be undefined.

Left shift can be used to multiply an integer by powers of 2 as in

inti=7;// Decimal 7 is Binary (2^2) + (2^1) + (2^0) = 0000 0111intj=3;// Decimal 3 is Binary         (2^1) + (2^0) = 0000 0011k=(i<<j);// Left shift operation multiplies the value by 2 to the power of j in decimal// Equivalent to adding j zeros to the binary representation of i// 56 = 7 * 2^3// 0011 1000 = 0000 0111 << 0000 0011

Example: a simple addition program

The following program adds two operands using AND, XOR and left shift (<<).

#include<stdio.h>intmain(void){unsignedintx=3,y=1,sum,carry;sum=x^y;// x XOR ycarry=x&y;// x AND ywhile(carry!=0){carry=carry<<1;// left shift the carryx=sum;// initialize x as sumy=carry;// initialize y as carrysum=x^y;// sum is calculatedcarry=x&y;/* carry is calculated, the loop condition is                           evaluated and the process is repeated until                           carry is equal to 0.                        */}printf("%u\n",sum);// the program will print 4return0;}

Bitwise assignment operators

C provides a compound assignment operator for each binary arithmetic and bitwise operation. Each operator accepts a left operand and a right operand, performs the appropriate binary operation on both and stores the result in the left operand. [6]

The bitwise assignment operators are as follows.

SymbolOperator
&=bitwise AND assignment
|=bitwise inclusive OR assignment
^=bitwise exclusive OR assignment
<<=left shift assignment
>>=right shift assignment

Logical equivalents

Four of the bitwise operators have equivalent logical operators. They are equivalent in that they have the same truth tables. However, logical operators treat each operand as having only one value, either true or false, rather than treating each bit of an operand as an independent value. Logical operators consider zero false and any nonzero value true. Another difference is that logical operators perform short-circuit evaluation.

The table below matches equivalent operators and shows a and b as operands of the operators.

BitwiseLogical
a & ba && b
a | ba || b
a ^ ba != b
~a!a

!= has the same truth table as ^ but unlike the true logical operators, by itself != is not strictly speaking a logical operator. This is because a logical operator must treat any nonzero value the same. To be used as a logical operator != requires that operands be normalized first. A logical not applied to both operands won’t change the truth table that results but will ensure all nonzero values are converted to the same value before comparison. This works because ! on a zero always results in a one and ! on any nonzero value always results in a zero.

Example:

/* Equivalent bitwise and logical operator tests */#include<stdio.h>voidtestOperator(char*name,unsignedcharwas,unsignedcharexpected);intmain(void){// -- Bitwise operators -- ////Truth tables packed in bitsconstunsignedcharoperand1=0x0A;//0000 1010constunsignedcharoperand2=0x0C;//0000 1100constunsignedcharexpectedAnd=0x08;//0000 1000constunsignedcharexpectedOr=0x0E;//0000 1110constunsignedcharexpectedXor=0x06;//0000 0110constunsignedcharoperand3=0x01;//0000 0001constunsignedcharexpectedNot=0xFE;//1111 1110testOperator("Bitwise AND",operand1&operand2,expectedAnd);testOperator("Bitwise  OR",operand1|operand2,expectedOr);testOperator("Bitwise XOR",operand1^operand2,expectedXor);testOperator("Bitwise NOT",~operand3,expectedNot);printf("\n");// -- Logical operators -- //constunsignedcharF=0x00;//ZeroconstunsignedcharT=0x01;//Any nonzero value// Truth tables packed in arraysconstunsignedcharoperandArray1[4]={T,F,T,F};constunsignedcharoperandArray2[4]={T,T,F,F};constunsignedcharexpectedArrayAnd[4]={T,F,F,F};constunsignedcharexpectedArrayOr[4]={T,T,T,F};constunsignedcharexpectedArrayXor[4]={F,T,T,F};constunsignedcharoperandArray3[2]={F,T};constunsignedcharexpectedArrayNot[2]={T,F};inti;for(i=0;i<4;i++){testOperator("Logical AND",operandArray1[i]&&operandArray2[i],expectedArrayAnd[i]);}printf("\n");for(i=0;i<4;i++){testOperator("Logical  OR",operandArray1[i]||operandArray2[i],expectedArrayOr[i]);}printf("\n");for(i=0;i<4;i++){//Needs ! on operand's in case nonzero values are differenttestOperator("Logical XOR",!operandArray1[i]!=!operandArray2[i],expectedArrayXor[i]);}printf("\n");for(i=0;i<2;i++){testOperator("Logical NOT",!operandArray3[i],expectedArrayNot[i]);}printf("\n");return0;}voidtestOperator(char*name,unsignedcharwas,unsignedcharexpected){char*result=(was==expected)?"passed":"failed";printf("%s %s, was: %X expected: %X \n",name,result,was,expected);}

The output of the above program will be

 Bitwise AND passed, was: 8 expected: 8  Bitwise  OR passed, was: E expected: E  Bitwise XOR passed, was: 6 expected: 6  Bitwise NOT passed, was: FE expected: FE    Logical AND passed, was: 1 expected: 1  Logical AND passed, was: 0 expected: 0  Logical AND passed, was: 0 expected: 0  Logical AND passed, was: 0 expected: 0    Logical  OR passed, was: 1 expected: 1  Logical  OR passed, was: 1 expected: 1  Logical  OR passed, was: 1 expected: 1  Logical  OR passed, was: 0 expected: 0    Logical XOR passed, was: 0 expected: 0  Logical XOR passed, was: 1 expected: 1  Logical XOR passed, was: 1 expected: 1  Logical XOR passed, was: 0 expected: 0    Logical NOT passed, was: 1 expected: 1  Logical NOT passed, was: 0 expected: 0

See also

Related Research Articles

<span class="mw-page-title-main">Arithmetic shift</span> Shift operator in computer programming

In computer programming, an arithmetic shift is a shift operator, sometimes termed a signed shift. The two basic types are the arithmetic left shift and the arithmetic right shift. For binary numbers it is a bitwise operation that shifts all of the bits of its operand; every bit in the operand is simply moved a given number of bit positions, and the vacant bit-positions are filled in. Instead of being filled with all 0s, as in logical shift, when shifting to the right, the leftmost bit is replicated to fill in all the vacant positions.

In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral at the level of its individual bits. 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.

Two's complement is a mathematical operation to reversibly convert a positive binary number into a negative binary number with equivalent negative value, using the binary digit with the greatest place value as the sign to indicate whether the binary number is positive or negative. It is used in computer science as the most common method of representing signed integers on computers, and more generally, fixed point binary values. When the most significant bit is 1, the number is signed as negative; and when the most significant bit is 0 the number is signed as positive (see Converting from two's complement representation, below).

The syntax of the C programming language is the set of rules governing writing of software in the C language. It is designed to allow for programs that are extremely terse, have a close relationship with the resulting object code, and yet provide relatively high-level data abstraction. C was the first widely successful high-level language for portable operating-system development.

In computer science, a mask or bitmask is data that is used for bitwise operations, particularly in a bit field. Using a mask, multiple bits in a byte, nibble, word, etc. can be set either on or off, or inverted from on to off in a single bitwise operation. An additional use of masking involves predication in vector processing, where the bitmask is used to select which element operations in the vector are to be executed and which are not.

In computer programming, undefined behavior (UB) is the result of executing a program whose behavior is prescribed to be unpredictable, in the language specification to which the computer code adheres. This is different from unspecified behavior, for which the language specification does not prescribe a result, and implementation-defined behavior that defers to the documentation of another component of the platform.

This is a list of operators in the C and C++ programming languages. All the operators listed exist in C++; the column "Included in C", states whether an operator is also present in C. Note that C does not support operator overloading.

The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string of bits, this is the number of 1's in the string, or the digit sum of the binary representation of a given number and the ℓ₁ norm of a bit vector. In this binary case, it is also called the population count, popcount, sideways sum, or bit summation.

A bit array is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level parallelism in hardware to perform operations quickly. A typical bit array stores kw bits, where w is the number of bits in the unit of storage, such as a byte or word, and k is some nonnegative integer. If w does not divide the number of bits to be stored, some space is wasted due to internal fragmentation.

In computer science, a logical shift is a bitwise operation that shifts all the bits of its operand. The two base variants are the logical left shift and the logical right shift. This is further modulated by the number of bit positions a given value shall be shifted, such as shift left by 1 or shift right by n. Unlike an arithmetic shift, a logical shift does not preserve a number's sign bit or distinguish a number's exponent from its significand (mantissa); every bit in the operand is simply moved a given number of bit positions, and the vacant bit-positions are filled, usually with zeros, and possibly ones.

<span class="mw-page-title-main">Circular shift</span>

In combinatorial mathematics, a circular shift is the operation of rearranging the entries in a tuple, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse operation. A circular shift is a special kind of cyclic permutation, which in turn is a special kind of permutation. Formally, a circular shift is a permutation σ of the n entries in the tuple such that either

The computer programming languages C and Pascal have similar times of origin, influences, and purposes. Both were used to design their own compilers early in their lifetimes. The original Pascal definition appeared in 1969 and a first compiler in 1970. The first version of C appeared in 1972.

<span class="mw-page-title-main">C data types</span> Data types supported by the C programming language

In the C programming language, data types constitute the semantics and characteristics of storage of data elements. They are expressed in the language syntax in form of declarations for memory locations or variables. Data types also determine the types of operations or methods of processing of data elements.

The bitap algorithm is an approximate string matching algorithm. The algorithm tells whether a given text contains a substring which is "approximately equal" to a given pattern, where approximate equality is defined in terms of Levenshtein distance – if the substring and pattern are within a given distance k of each other, then the algorithm considers them equal. The algorithm begins by precomputing a set of bitmasks containing one bit for each element of the pattern. Then it is able to do most of the work with bitwise operations, which are extremely fast.

A bit field is a data structure that consists of one or more adjacent bits which have been allocated for specific purposes, so that any single bit or group of bits within the structure can be set or inspected. A bit field is most commonly used to represent integral types of known, fixed bit-width, such as single-bit Booleans.

Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a word. Computer programming tasks that require bit manipulation include low-level device control, error detection and correction algorithms, data compression, encryption algorithms, and optimization. For most other tasks, modern programming languages allow the programmer to work directly with abstractions instead of bits that represent those abstractions.

sizeof is a unary operator in the programming languages C and C++. It generates the storage size of an expression or a data type, measured in the number of char-sized units. Consequently, the construct sizeof (char) is guaranteed to be 1. The actual number of bits of type char is specified by the preprocessor macro CHAR_BIT, defined in the standard include file limits.h. On most modern computing platforms this is eight bits. The result of sizeof has an unsigned integer type that is usually denoted by size_t.

<span class="mw-page-title-main">Computation of cyclic redundancy checks</span> Overview of the computation of cyclic redundancy checks

Computation of a cyclic redundancy check is derived from the mathematics of polynomial division, modulo two. In practice, it resembles long division of the binary message string, with a fixed number of zeroes appended, by the "generator polynomial" string except that exclusive or operations replace subtractions. Division of this type is efficiently realised in hardware by a modified shift register, and in software by a series of equivalent algorithms, starting with simple code close to the mathematics and becoming faster through byte-wise parallelism and space–time tradeoffs.

<span class="mw-page-title-main">Arithmetic logic unit</span> Combinational digital circuit

In computing, an arithmetic logic unit (ALU) is a combinational digital circuit that performs arithmetic and bitwise operations on integer binary numbers. This is in contrast to a floating-point unit (FPU), which operates on floating point numbers. It is a fundamental building block of many types of computing circuits, including the central processing unit (CPU) of computers, FPUs, and graphics processing units (GPUs).

In computer software and hardware, find first set (ffs) or find first one is a bit operation that, given an unsigned machine word, designates the index or position of the least significant bit set to one in the word counting from the least significant bit position. A nearly equivalent operation is count trailing zeros (ctz) or number of trailing zeros (ntz), which counts the number of zero bits following the least significant one bit. The complementary operation that finds the index or position of the most significant set bit is log base 2, so called because it computes the binary logarithm ⌊log2(x)⌋. This is closely related to count leading zeros (clz) or number of leading zeros (nlz), which counts the number of zero bits preceding the most significant one bit. There are two common variants of find first set, the POSIX definition which starts indexing of bits at 1, herein labelled ffs, and the variant which starts indexing of bits at zero, which is equivalent to ctz and so will be called by that name.

References

  1. ↑ Kernighan; Dennis M. Ritchie (March 1988). The C Programming Language (2nd ed.). Englewood Cliffs, NJ: Prentice Hall. ISBN   0-13-110362-8. Archived from the original on 2019-07-06. Retrieved 2019-09-07. Regarded by many to be the authoritative reference on C.
  2. 1 2 "Tutorials - Bitwise Operators and Bit Manipulations in C and C++". cprogramming.com.
  3. ↑ "Exclusive-OR Gate Tutorial". Basic Electronics Tutorials.
  4. ↑ "C++ Notes: Bitwise Operators". fredosaurus.com.
  5. ↑ "ISO/IEC 9899:2011 - Information technology -- Programming languages -- C". www.iso.org.
  6. ↑ "Compound assignment operators". IBM. International Business Machines. Retrieved 29 January 2022.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.