FACTOID # 13: New York has America's lowest percentage of residents who are veterans.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Bitwise operation

In computer programming, a bitwise operation operates on one or two bit patterns or binary numerals at the level of their individual bits. On many computers, bitwise operations are slightly faster than addition and subtraction operations and significantly faster than multiplication and division operations. Programming redirects here. ... Bit pattern is the pattern of bitwise operations. ... The binary numeral system, or base-2 number system, is a numeral system that represents numeric values using two symbols, usually 0 and 1. ... This article is about the unit of information. ... This article is about the machine. ...

Contents

Bitwise operators

NOT

The bitwise NOT, or complement, is a unary operation which performs logical negation on each bit, forming the ones' complement of the given binary value. Digits which were 0 become 1, and vice versa. For example: In mathematics, a unary operation is an operation with only one operand. ... Negation (i. ... In mathematics, signed numbers in some arbitrary base is done in the usual way, by prefixing it with a - sign. ...

 NOT 0111 = 1000 

In many programming languages (including those in the C family), the bitwise NOT operator is "~" (tilde). This operator must not be confused with the "logical not" operator, "!" (exclamation point), which treats the entire value as a single Boolean — changing a true value to false, and vice versa. The "logical not" is not a bitwise operation. C is a general-purpose, block structured, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ... For the baseball player known as the Big Tilde, see Magglio Ordóñez. ... In computer science, the Boolean datatype, sometimes called the logical datatype, is a primitive datatype having two values: one and zero (which are equivalent to true and false). ...


OR

A bitwise OR takes two bit patterns of equal length, and produces another one of the same length by matching up corresponding bits (the first of each; the second of each; and so on) and performing the logical inclusive OR operation on each pair of corresponding bits. In each pair, the result is 1 if the first bit is 1 OR the second bit is 1 (or both), and otherwise the result is 0. For example: OR logic gate. ...

 0101 OR 0011 = 0111 

In the C programming language family, the bitwise OR operator is "|" (pipe). Again, this operator must not be confused with its Boolean "logical or" counterpart, which treats its operands as Boolean values, and is spelled "||" (two pipes). The symbol (|) has various names that refer to differing, yet sometimes related semantics: One of the more popular names is the Sheffer stroke, though often referred to as a pipe (by the Unix community) and Vertical bar, verti-bar, vertical line or divider line by others. ...


The bitwise OR may be used in situations where a set of bits are used as flags; the bits in a single binary numeral may each represent a distinct Boolean variable. Applying the bitwise OR operation to the numeral along with a bit pattern containing 1 in some positions will result in a new numeral with those bits set. For example: In computer programming, flag refers to one or more bits that are used to store a binary value or code that has an assigned meaning. ... In computer science, the Boolean datatype, sometimes called the logical datatype, is a primitive datatype having two values: one and zero (which are equivalent to true and false). ...

 0010 

can be considered as a set of four flags. The first, second, and fourth flags are not set (0); the third flag is set (1). The first flag may be set by applying the bitwise OR to this value, along with another value in which only the first flag is set:

 0010 OR 1000 = 1010 

This technique is often used to conserve space in programs dealing with large numbers of Boolean values.


XOR

A bitwise exclusive or takes two bit patterns of equal length and performs the logical XOR operation on each pair of corresponding bits. The result in each position is 1 if the two bits are different, and 0 if they are the same. For example: Exclusive disjunction, also known as exclusive or and symbolized by XOR or EOR, is a logical operation on two operands that results in a logical value of true if and only if one of the operands, but not both, has a value of true. ...

 0101 XOR 0011 = 0110 

In the C programming language family, the bitwise XOR operator is "^" (caret). For other uses, see Caret (disambiguation). ...


Assembly language programmers sometimes use the XOR operation as a short-cut to set the value of a register to zero. Performing XOR on a value against itself always yields zero, and on many architectures, this operation requires fewer CPU clock cycles than the sequence of operations that may be required to load a zero value and save it to the register. See the terminology section, below, regarding inconsistent use of the terms assembly and assembler. ... In computer architecture, a processor register is a small amount of very fast computer memory used to speed the execution of computer programs by providing quick access to frequently used values—typically, these values are involved in multiple expression evaluations occurring within a small region on the program. ... CPU redirects here. ...


The bitwise XOR may also be used to toggle flags in a set of bits. Given a bit pattern: Look up Toggle in Wiktionary, the free dictionary. ...

 0010 

The first and third bits may be toggled simultaneously by a bitwise XOR with another bit pattern containing 1 in the first and third positions:

 0010 XOR 1010 = 1000 

This technique may be used to manipulate bit patterns representing sets of Boolean variables.


See also

It has been suggested that this article or section be merged with swap (computer science). ... XOR linked lists are a curious use of the bitwise exclusive disjunction (XOR) operation to decrease storage requirements for doubly-linked lists. ...

AND

A bitwise AND takes two binary representations of equal length and performs the logical AND operation on each pair of corresponding bits. In each pair, the result is 1 if the first bit is 1 AND the second bit is 1. Otherwise, the result is 0. For example: AND Logic Gate In logic and mathematics, logical conjunction (usual symbol and) is a two-place logical operation that results in a value of true if both of its operands are true, otherwise a value of false. ...

 0101 AND 0011 = 0001 

In the C programming language family, the bitwise AND operator is "&" (ampersand). Again, this operator must not be confused with its Boolean "logical and" counterpart, which treats its operands as Boolean values, and is written "&&" (two ampersands). An ampersand (&), also commonly called an and sign is a logogram representing the conjunction and. ...


The bitwise AND may be used to perform a bit mask operation. This operation may be used to isolate part of a string of bits, or to determine whether a particular bit is 1 or 0. For example, given a bit pattern:

 0011 

To determine whether the third bit is 1, a bitwise AND is applied to it and another bit pattern containing 1 in the third bit:

 0011 AND 0010 = 0010 

Since the result is 0010 (non-zero), the third bit in the original pattern was 1. Using bitwise AND in this manner is called bit masking, by analogy to the use of masking tape to cover, or mask, portions that should not be altered, or are not of interest. In this case, the 0 values mask the bits that are not of interest. Masking tape Masking tape is a type of adhesive tape made of easy-to-tear paper backed with a weak adhesive. ...


The bitwise AND can also be combined with the bitwise NOT to clear bits. For example:

 0110 

The second flag may be cleared (i.e. set to 0) by applying the bitwise AND to this value, along with the complement of another value in which only the second flag is set:

 NOT 0100 = 1011 0110 AND 1011 = 0010 

Bit shifts

The bit shifts are sometimes considered bitwise operations, since they operate on the binary representation of an integer instead of its numerical value; however, the bit shifts do not operate on pairs of corresponding bits, and therefore cannot properly be called bit-wise operations. In this operation, the digits are moved, or shifted, to the left or right. Registers in a computer processor have a fixed number of available bits for storing numerals, so some bits will be "shifted out" of the register at one end, while the same number of bits are "shifted in" from the other end; the differences between bit shift operators lie in how they compute the values of those shifted-in bits. In computer architecture, a processor register is a small amount of very fast computer memory used to speed the execution of computer programs by providing quick access to frequently used values—typically, these values are involved in multiple expression evaluations occurring within a small region on the program. ...


Arithmetic shift

Main article: Arithmetic shift
Left arithmetic shift
Left arithmetic shift
Right arithmetic shift
Right arithmetic shift

In an arithmetic shift, the bits that are shifted out of either end are discarded. In a left arithmetic shift, zeros are shifted in on the right; in a right arithmetic shift, the sign bit is shifted in on the left, thus preserving the sign of the operand. This example uses an 8-bit register: In telecommunication, an arithmetic shift is a shift, applied to the representation of a number in a fixed radix numeration system and in a fixed-point representation system, and in which only the characters representing the fixed-point part of the number are moved. ... Image File history File links Rotate_left_logically. ... Image File history File links Rotate_left_logically. ... Image File history File links Rotate_right_arithmetically. ... Image File history File links Rotate_right_arithmetically. ... In computer science the sign bit is the bit in a computer numbering format which indicates the sign of the number. ...

 00010111 LEFT-SHIFT = 00101110 
 00010111 RIGHT-SHIFT = 00001011 

In the first case, the leftmost digit was shifted past the end of the register, and a new 0 was shifted into the rightmost position. In the second case, the rightmost 1 was shifted out (perhaps into the carry flag), and a new 0 was copied into the leftmost position, preserving the sign of the number. Multiple shifts are sometimes shortened to a single shift by some number of digits. For example:

 00010111 LEFT-SHIFT-BY-TWO = 01011100 

A left arithmetic shift by n is equivalent to multiplying by 2n (provided the value does not overflow), while a right arithmetic shift by n of a two's complement value is equivalent to dividing by 2n and rounding toward negative infinity. If the binary number is treated as ones' complement, then the same right-shift operation results in division by 2n and rounding toward zero. The term arithmetic overflow or simply overflow has the following meanings. ... The twos complement of a binary number is the value obtained by subtracting the number from a large power of two (specifically, from 2N for an N-bit twos complement). ... In mathematics, the extended real number line is obtained from the real number line R by adding two elements: +∞ and −∞ (pronounced plus infinity and minus infinity). These new elements are not real numbers. ... In mathematics, signed numbers in some arbitrary base is done in the usual way, by prefixing it with a - sign. ...


Logical shift

Main article: Logical shift
Logical shift right
Logical shift right
Logical shift left
Logical shift left

In a logical shift, the bits that are shifted out are discarded, and zeros are shifted in (on either end). Therefore, the logical and arithmetic left-shifts are exactly the same operation. However, the logical right-shift inserts bits with value 0 instead of copies of the sign bit. Hence the logical shift is suitable for unsigned binary numbers, while the arithmetic shift is suitable for signed two's complement binary numbers.
In computer science, a logical shift is a shift operator that shifts all the bits of its operand. ... Image File history File links Rotate_right_logically. ... Image File history File links Rotate_right_logically. ... Image File history File links Rotate_left_logically. ... Image File history File links Rotate_left_logically. ... The twos complement of a binary number is the value obtained by subtracting the number from a large power of two (specifically, from 2N for an N-bit twos complement). ...


Rotate no carry

Main article: Circular shift
Right circular shift or rotate
Right circular shift or rotate
Left circular shift or rotate
Left circular shift or rotate

Another form of shift is the circular shift or bit rotation. In this operation, the bits are "rotated" as if the left and right ends of the register were joined. The value that is shifted in on the right during a left-shift is whatever value was shifted out on the left, and vice versa. This operation is useful if it is necessary to retain all the existing bits, and is frequently used in digital cryptography.
In combinatorial mathematics, a circular shift is a permutation of the entries in a tuple where the last element becomes the first element and all the other elements are shifted, or where the first element becomes the last element and all the other are shifted. ... Image File history File links Rotate_right. ... Image File history File links Rotate_right. ... Image File history File links Rotate_left. ... Image File history File links Rotate_left. ... The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and the verb γράφω gráfo write or λεγειν legein to speak) is the study of message secrecy. ...


Rotate through carry

Right rotate through carry
Right rotate through carry
Left rotate through carry
Left rotate through carry

Rotate through carry is similar to the rotate no carry operation, but the two ends of the register are considered to be separated by the carry flag. The bit that is shifted in (on either end) is the old value of the carry flag, and the bit that is shifted out (on the other end) becomes the new value of the carry flag. Image File history File links Rotate_right_through_carry. ... Image File history File links Rotate_right_through_carry. ... Image File history File links Rotate_left_through_carry. ... Image File history File links Rotate_left_through_carry. ... In computer processors carry flag is a single bit in a system status (flag) register used to indicate when an arithmetic carry or borrow has been generated out of the most significant ALU bit position. ...


A single rotate through carry can simulate a logical or arithmetic shift of one position by setting up the carry flag beforehand. For example, if the carry flag contains 0, then x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE is a logical right-shift, and if the carry flag contains a copy of the sign bit, then x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE is an arithmetic right-shift. For this reason, some microcontrollers such as PICs just have rotate and rotate through carry, and don't bother with arithmetic or logical shift instructions. PIC microcontrollers in DIP and QFN packages PIC is a family of Harvard architecture microcontrollers made by Microchip Technology, derived from the PIC1650 originally developed by General Instruments Microelectronics Division. ...


Rotate through carry is especially useful when performing shifts on numbers larger than the processor's native word size, because if a large number is stored in two registers, the bit that is shifted off the end of the first register must come in at the other end of the second. With rotate-through-carry, that bit is "saved" in the carry flag during the first shift, ready to shift in during the second shift without any extra preparation.
In computer hardware terminology, word size (word length) is the number of bits that a CPU can process at one time (the word). ...


Shifts in C, C++, and Java

In C, C++ and many other languages that borrow syntax from them, the left and right shift operators are "<<" and ">>", respectively. The number of places to shift is given as the second argument to the shift operators. For example,

 x = y << 2; 

assigns x the result of shifting y to the left by two digits.


In C and C++, computations on unsigned values use logical shifts; computations on signed values may use logical or arithmetic shifts, depending on the implementation.[1]


In Java, all integer types are signed, and the "<<" and ">>" operators perform arithmetic shifts. Java adds the operator ">>>" to perform logical right shifts, but since the logical and arithmetic left-shift operations are identical, there is no "<<<" operator in Java. These general rules are affected in several ways by the default type promotions; for example, since the eight-bit type byte is promoted to int in shift-expressions,[2] the expression "b >>> 2" effectively performs an arithmetic shift of the byte value b instead of a logical shift. Such effects can be mitigated by judicious use of casts or bitmasks; for example, "(b & 0xFF) >>> 2" effectively results in a logical shift. Java language redirects here. ... In computer science, type conversion or typecasting refers to changing an entity of one data type into another. ... In computer science, a mask is some data that, along with an operation, are used in order to extract information stored elsewhere. ...


Applications

Bitwise operations are necessary for much low-level programming, such as writing device drivers, low-level graphics, communications protocol packet assembly and decoding.


Although machines often have efficient built-in instructions for performing arithmetic and logical operations, in fact all these operations can be performed just by combining the bitwise operators and zero-testing in various ways. For example, here is a pseudocode example showing how to multiply two arbitrary integers a and b using only bitshifts and addition: Pseudocode (derived from pseudo and code) is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of programming languages, but omits detailed subroutines, variable declarations or language-specific syntax. ...

 c := 0 while b ≠ 0 if (b and 1) ≠ 0 c := c + a shift a left by one shift b right by one return c  

See also

Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than byte. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... Boolean algebra is the finitary algebra of two values. ... In computer science, the double dabble algorithm is used to convert binary numbers into decimal (in particular, binary-coded decimal, or BCD, notation). ... A logic gate performs a logical operation on one or more logic inputs and produces a single logic output. ... In logical calculus, logical operators or logical connectors serve to connect statements into more complicated compound statements. ... An example Karnaugh map The Karnaugh map, also known as a Veitch diagram (K-map or KV-map for short), is a tool to facilitate management of Boolean algebraic expressions. ...

References

  1. ^ JTC1/SC22/WG14 N843 "C programming language", section 6.5.7#5
  2. ^ "The Java Language Specification, Second Edition", sections 15.19 (shift operators) and 5.6.1 (unary numeric promotion)

External links

  • Division using bitshifts

  Results from FactBites:
 
MSNP8:Bitwise AND - MSNPiki (1546 words)
Bitwise NOT is useful in finding the one's complement of a binary numeral, and may be an intermediate step in finding the two's complement of the same numeral.
The bitwise OR may be used in situations where a set of bits are used as flags; the bits in a single binary numeral may each represent a distinct Boolean variable.
This operation may be used to isolate part of a string of bits, or to determine whether a particular bit is 1 or 0.
Bitwise - CryptoDox (838 words)
Bitwise NOT is useful in finding the one's complement of a binary numeral, and may be an intermediate step in finding the two's complement of the same numeral.
The bitwise OR may be used in situations where a set of bits are used as flags; the bits in a single binary numeral may each represent a distinct Boolean variable.
This operation may be used to isolate part of a string of bits, or to determine whether a particular bit is 1 or 0.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m