Most significant bit

In computing, the most significant bit (msb) is the bit position in a binary number having the greatest value. The msb is sometimes referred to as the left-most bit, due to the convention in positional notation of writing more significant digits further to the left.

The msb can also correspond to the sign of a signed binary number in one or two's complement notation. "1" meaning negative and "0" meaning positive.

MSB, in all capitals, can also stand for "most significant byte". The meaning is parallel to the above: it is the byte (or octet) in that position of a multi-byte number which has the greatest potential value.

By extension, the most significant bits (plural) are the bits of the number closest to, and including, the msb.

The unsigned binary representation of decimal 149, with the msb highlighted. The msb in an 8-bit binary number represents a value of 128 decimal. The lsb represents a value of 1.

Conventions

In referencing specific bits within a binary number, it is common to assign each bit a bit number, ranging from zero upwards to one less than the number of bits in the number. However, the order used for this assignment may be in either direction, and both orderings are used (in different contexts). This is one reason why "msb" is often used to designate the high-order bit instead of a bit number (which has greater potential for confusion).

Transmission

With 802.5 and FDDI, the most significant bit is transmitted first.[1]

Computing position of most significant 1 bit of an integer

The following code example for the C language is an algorithm to compute the position of most significant 1 bit of a 32 bit integer. ^[1] Operator '>>' represents 'unsigned right shift'.

/**
 * Returns the most significant bit position of n from 0 to 31.
 * -1 is returned if n is 0.
 */
int mostSignificantBitPosition(unsigned int n) {
  int pos = 0;
  int tmp;
  tmp = n >> 16;
  if (tmp != 0) { n = tmp; pos = pos + 16; }
  tmp = n >> 8;
  if (tmp != 0) { n = tmp; pos = pos + 8; }
  tmp = n >> 4;
  if (tmp != 0) { n = tmp; pos = pos + 4; }
  tmp = n >> 2;
  if (tmp != 0) { n = tmp; pos = pos + 2; }
  tmp = n >> 1;
  if (tmp != 0) { n = tmp; pos = pos + 1; }
  return pos + n - 1;
}

// C# code to return the index of the MSB.  MSB(0)=0
public static int MostSignificantBit (UInt32 n)				
{
     int b = 0;
     if (0 != (n & (~0u << (1 << 4)))) { b |= (1 << 4); n >>= (1 << 4); }
     if (0 != (n & (~0u << (1 << 3)))) { b |= (1 << 3); n >>= (1 << 3); }
     if (0 != (n & (~0u << (1 << 2)))) { b |= (1 << 2); n >>= (1 << 2); }
     if (0 != (n & (~0u << (1 << 1)))) { b |= (1 << 1); n >>= (1 << 1); }
     if (0 != (n & (~0u << (1 << 0)))) { b |= (1 << 0); }
     return b;
}

// C# code to return the index of the MSB.  MSB(0)=0
public static int MostSignificantBit(UInt64 n)
{
     int b = 0;
     if (0 != (n & (~0uL << (1 << 5)))) { b |= (1 << 5); n >>= (1 << 5); }
     if (0 != (n & (~0uL << (1 << 4)))) { b |= (1 << 4); n >>= (1 << 4); }
     if (0 != (n & (~0uL << (1 << 3)))) { b |= (1 << 3); n >>= (1 << 3); }
     if (0 != (n & (~0uL << (1 << 2)))) { b |= (1 << 2); n >>= (1 << 2); }
     if (0 != (n & (~0uL << (1 << 1)))) { b |= (1 << 1); n >>= (1 << 1); }
     if (0 != (n & (~0uL << (1 << 0)))) { b |= (1 << 0); }
     return b;
}

For interpreted languages, the $\log _{2}$ function is generally faster and more succinct to use. The following example expresses this method using Python.

from math import log
def msb_pos(n):
    return int(log(n, 2))

Since Java 1.5, the Java standard library provides the Integer.numberOfLeadingZeros(int) and Long.numberOfLeadingZeros(long) methods to compute the number of leading zeros in 32-bit and 64-bit integers, respectively. This number is equal to (the width of the integer) - 1 - (the position of the most significant 1 bit).

References

^ Warren Jr., Henry S. (2002), Hacker's Delight, Addison Wesley, pp. pp. 77, ISBN 978-0201914658 {{citation}}: |pages= has extra text (help)

Conventions

Transmission

Computing position of most significant 1 bit of an integer

References

See also