Home * Programming * Data * Nibble

A Nibble, also called Nybble, is a term for a four-bit aggregation. It is the half of a Byte. With four bits one can distinct 16 states, 0000B to 1111B as binary code, representing decimal numbers from 0 to 15.

One hexadecimal digit {'0'..'9', 'A' ..'F'} exactly covers one nibble. Since bytes are considered atomic items, nibble endianness is no issue. Per definition a least significant nibble covers the least significant bits 0..3 of a byte, the most significant nibble the bits 4..7 of a byte. If we write the value of a byte with two hexadecimal digits, we use the usual big-endian notation, e.g. in 0x3F, '3' is the most significant nibble (digit) and 'F' the least significant one.

Nibble as Type

A nibble is appropriate to hold the value ranges of

Signed Nibbles

In a signed nibble Two's Complement representation, bit 3 is interpreted as sign bit.
binary
hex
unsigned
signed
0000B
0x0
0
0
0001B
0x1
1
1
0010B
0x2
2
2
0011B
0x3
3
3
0100B
0x4
4
4
0101B
0x5
5
5
0110B
0x6
6
6
0111B
0x7
7
7
1000B
0x8
8
-8
1001B
0x9
9
-7
1010B
0xA
10
-6
1011B
0xB
11
-5
1100B
0xC
12
-4
1101B
0xD
13
-3
1110B
0xE
14
-2
1111B
0xF
15
-1

Array of Nibbles

An array of N nibbles can be declared as array of (N+1)/2 bytes, for instance for a dense Board Representation.
BYTE nibbleBoard[32];
And this is how to extract piece-codes from a that board:
int getPiece(int square) {
   int shift = (square & 1)  << 2; // 4 or 0
   return nibbleBoard[square >> 1] >> shift) & 15;
}
 
void setPiece(int square, int piece) {
   int shift = (square & 1) << 2; // 4 or 0
   nibbleBoard[square >> 1] &= (BYTE)(  240 >> shift);
   nibbleBoard[square >> 1] |= (BYTE)(piece << shift);
}
This is considerable more effort than simple array access with at least byte granulation, in both code size and runtime - and array board representations are likely not member of a search stack, but updated incrementally during make and unmake, it does not seem to make sense to use nibbleBoards as mentioned to save some data bytes. However, Vladan Vučković proposed the Nibble-Board as used in his program Axon and its parallel version Achilles, dubbed Compact Chessboard Representation, declared as array of eight 32-bit or four 64-bit integers, intended for register processing [1] [2].

SWAR Nibbles

To apply 'add' or 'sub' on vectors of nibbles (or any arbitrary structure) SWAR-wise within a 32-bit or 64-bit register, we have to take care carries and borrows don't wrap around. Thus we apply a mask of all most significant bits (H) and 'add' in two steps, one 'add' with MSB clear and one add modulo 2 aka 'xor' for the MSB itself. For nibble-wise math of a vector of eight nibbles inside a 32-bit register, H is 0x88888888 and L is 0x11111111.
SWAR add z = x + y
    z = ((x &~H) + (y &~H)) ^ ((x ^ y) & H)
 
SWAR sub z = x - y
    z = ((x | H) - (y &~H)) ^ ((x ^~y) & H)
 
SWAR average z = (x+y)/2 based on x + y = (x^y) + 2*(x&y)
    z = (x & y) + (((x ^ y) & ~L) >> 1)

See also


Publications


External Links


References

  1. ^ Vladan Vučković (2008). The Compact Chessboard Representation. ICGA Journal, Vol. 31, No. 3
  2. ^ Vladan Vučković (2012). An Alternative Efficient Chessboard Representation based on 4-Bit Piece Coding. Yugoslav Journal of Operations Research, Vol. 22, No. 1, pdf

What links here?


Up one Level