Protocols/MSNP/MSNP8/Bitwise AND

MSNP Protocol

Version 8

General

Overview • Glossary

Payload Commands • Names

Bitwise AND

Connecting

Authentication • Presence

Challenges • Getting Details

Setting Details • Messages

Miscellaneous

Example Session

Messaging

Authentication • Miscellaneous

Messages • Example Session

Overview

Introduction • Terms • Clients

Reference

Error List • Commands • Relying Party Suite • Spotlife

Services

XMPP • HTTP Gateway • Tabs • Activities

Documentation

Development Tools • MSNP Grid

Polygamy • URLs used by MSN

Documents

Protocol Versions

Version 21

Version 18

Version 16

Version 15

Version 14

Version 13

Version 12

Version 11

Version 9

Version 8

Version 2

MSNC

Introduction • P2P • Object Descriptor • Display Pictures • File Transfer

Scenarios

Microsoft Messenger for Mac

MSNP on WebTV (MSNTV)

In Wikipedia:computer programming, a bitwise operation operates on one or two Wikipedia:bit patterns or binary numerals at the level of their individual Wikipedia:bits. On many Wikipedia:computers, bitwise operations are slightly faster than addition and subtraction operations and significantly faster than multiplication and division operations.

Bitwise operators

NOT

A bitwise NOT or complement is a Wikipedia:unary operation which performs logical Wikipedia:negation on each bit. 0 digits become 1, and vice versa. For example:

NOT 0111
  = 1000

In the C and Wikipedia:C++ programming languages, and even in some interpreted languages like Python and Wikipedia:Perl, the bitwise NOT operator is "~" (tilde). For example:

x = ~y;

assigns x the result of "NOT y". This is different from the C and C++ logical "not" operator, "!" (exclamation point), which treats the entire numeral as a single Boolean value. For example:

x = !y;

assigns x a Boolean value of "true" if y is "false", or "false" if y is "true". In C and C++, a numerical value is interpreted as "true" if it is non-zero. (In C and C++, the relational, equality, and logical operators return an integer 1 for true and an integer 0 for false.) The logical "not" is not normally considered a bitwise operation, since it does not operate at the bit level.

Bitwise NOT is useful in finding the Wikipedia:one's complement of a binary numeral, and may be an intermediate step in finding the Wikipedia:two's complement of the same numeral.

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 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. Otherwise, the result is zero. For example:

   0101
OR 0011
 = 0111

In C/C++, the bitwise OR operator is "|" (Wikipedia:vertical bar/pipe). For example:

x = y | z;

assigns x the result of "y OR z". This is different from the C and C++ logical "or" operator, "||" (two vertical bars), which treats its operands as Boolean values, and results in "true" or "false".

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:

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 may be employed by programmers who are working under restrictions of memory space; one bit pattern can represent the states of several independent variables at once.

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:

    0101
XOR 0011
  = 0110

In C/C++, the bitwise XOR operator is "^" (Wikipedia:circumflex). For example:

x = y ^ z;

assigns x the result of "y XOR z".

Wikipedia: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.

The bitwise XOR may also be used to Wikipedia:toggle flags in a set of bits. Given a bit pattern:

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

• Wikipedia:Xor swap algorithm

AND

A bitwise AND takes two binary representations of equal length and performs the logical AND 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 zero. For example:

    0101
AND 0011
  = 0001

In C/C++, the bitwise AND operator is "&" (Wikipedia:ampersand). For example:

x = y & z;

assigns x the result of "y AND z". This is different from the C and C++ logical "and" operator, "&&", which takes two logical operands as input and produces a result of "true" or "false".

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 along with another bit pattern containing 1 in the third bit, and 0 in all other bits:

    0011
AND 0010
  = 0010

Since the result is 0010 (not 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 Wikipedia:masking tape to cover, or mask, portions that should not be altered, or are not of interest. The 0 values mask the bits that are not of concern, in this case.

Bit shift

The bit shift is sometimes considered a bitwise operation, since it operates on a set of bits. Unlike the above, the bit shift operates on the entire numeral, rather than on individual bits. 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 may be shifted past the "end" of the register; the different kinds of shift typically differ in what they do with the bits that are shifted past the end.

Arithmetic shift

File:ShiftLeft.JPG

Left shift

File:ArithmaticShiftRight.JPG

Right arithmetic shift

One common form of shift is the arithmetic shift; in this shift, the bits that move past the end disappear. The new spaces are filled with zero, in the case of a left arithmetic shift, or with the sign bit, in the case of a right arithmetic shift. This example uses a 4-bit register:

  0111 LEFT-SHIFT
= 1110

  0111 RIGHT-SHIFT
= 0011

In the first case, the leftmost 0 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 past the end (and is often in the carry flag though that can't usually be accessed in high level languages), and the sign bit 0 was copied into the leftmost position. Multiple shifts are sometimes shortened to a single shift by some number of digits. For example:

  0111 LEFT-SHIFT-BY-TWO
= 1100

In C/C++ (and many other languages), the left and right shift operators are "<<" and ">>", respectively. The number of places to shift is given as an argument to the shift operators. For example:

x = y << 2;

assigns x the result of shifting y to the left by two digits, using the arithmetic shift. It should be noted that when using the right bitwise shift operator >> in C or C++, the behavior is left up to the implementation whether to perform an arithmetic or a logical shift. Java clarifies this ambiguity with an additional operator for right bitwise logical shifts: the >>> operator. See the Logical shift section of this article for more about Java's >>> logical bitwise right shift operator.

A left arithmetic shift is equivalent to multiplying by two (provided the value does not overflow), while a right arithmetic shift is equivalent to dividing by two and rounding down for positive numbers but rounding up for negative numbers.

Logical shift

File:LogicalShiftRight.JPG

Right logical shift

The logical shift is similar to the arithmetic shift but when shifting right inserts a zero rather than performing sign extension. Hence the logical shift is suitable for unsigned binary numbers while the arithmetic shift is suitable for two's complement binary numbers. In the Java programming language, a logical shift operation can be performed using the >>> operator, which fills in all high order bits with zeros. Since both arithmetic and logical leftwise shifts produce identical results, there is no '<<<' operator in Java.

Rotate no carry

File:RotateRight.JPG Right circular shift or rotate

File:RotateLeft.JPG Left circular shift or rotate

Another form of shift is the circular shift or bit rotation. In this, the bits are "rotated" as if the left and right ends of the numeral were joined. Any digits which are shifted past the rightmost place are moved to the leftmost place, and vice-versa. This operation is useful if it is necessary to retain all the existing bits.

Rotate through carry

File:RotateRightThroughCarry.png Right rotate through carry

File:RotateLeftThroughCarry.png Left rotate through carry

This is similar to the rotate operation but the carry flag is considered to be between the ends of the numbers. This operation can be used as a logical or arithmetic shift by setting up the carry flag beforehand. 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. Rotate through carry is especially useful when performing shifts on numbers larger than the processor's native word size.

Applications

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 bit shift and addition:

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