Algo

SOurces §

bitachks -> https://graphics.stanford.edu/~seander/bithacks.html

DICT §

MSB-> most significant byte LSB-> least significant byte BE -> bi endian -> allow for both LE and BE

Endianness: §

order of bytes of word Big Endian, BE: MSB of word at smallest memory address Little Endian, LE: LSB of word at smallest memory address

EX: Given number 39998(stored as 32 bit binary), system with word size 32 bits num = 39998 00000000 00000000 10011100 00111110 0X 00 00 9C 3E memory addresses BE(HEX) LE(HEX) 00000000 00 3E
00000001 00 9C 00000002 9C 00 00000003 3E 00

EX: x86-64 -> LE, OpenRisc -> BE, ARM,AArch64 -> BE

check Endianness on linux $ lscpu | grep Endian

or

https://serverfault.com/a/163493 -n Do not output new lines —format=o2 -> two byte octal $echo-nI|od--format=o2|head--lines=1|cut--fields=2--delimiter=""|cut--characters=6$ echo -n I | od -to2 | head -n1 | cut -f2 -d” ” | cut -c6

Parity §

parity bit or check bit: ensure total number of 1-bit is even or odd count of 1-bit: T even -> 0 if T is even even -> 1 if T is odd odd -> 0 if T is odd odd -> 1 if T is even 1100 011 -> T=4 -> even=0, 1100 0110, odd=1, 1100 0111

Computing parity (1 if an odd number of bits set, 0 otherwise)

A-1 binary implication: start from LSb of A and go until you see a 1-bit flip from and including the 1-bit all the way to end(LSb) therefor -> A & (A-1) means settings the bits from the position of first 1-bit(starting from lsb) to end to zero since A-1 flips those bits and anding a bit with it’s flipped value is bit-val & !bit-val -> always zero

A+1 binary implication: start from lsb go till you hit a 0-bit flip it everything to right of it(lsb)

A & (A - 1) -> drops the lowest set bit A & ~(A - 1) -> isolates the lowest set bit

Native:

unsigned int v;       // word value to compute the parity of
bool parity = false;  // parity will be the parity of v
 
 
// each time we set everything to the right of and including the last 1-bit to zero
while (v)
{
  parity = !parity;
  v = v & (v - 1);
}

Lookuptable:

We use the four variations for a 2 bit pair and their parity bit to construct table 00 -> 0 01 -> 1 10 -> 1 11 -> 0

static const bool ParityTable256[256] = 
{
#   define P2(n) n, n^1, n^1, n
#   define P4(n) P2(n), P2(n^1), P2(n^1), P2(n)
#   define P6(n) P4(n), P4(n^1), P4(n^1), P4(n)
    P6(0), P6(1), P6(1), P6(0)
};
 
unsigned char b;  // byte value to compute the parity of
bool parity = ParityTable256[b];

this method doesn’t exactly scale where we have a counter that is a 64bit int it would require a tabel with 2^64 entries solution: fold it keep folding the 32 or 64 bit bit words in half till they reduce down to 8 this can be done with shifting the word by half its size(sets the fist half to zeros) and getting the xor of original and shifted version. this will not change the first half but now the second half is essentially representative of evenness or oddness ot total count of 1 in entire word since after xor if both bits were 0 or 1 the result is zero or even number of 1-bits if they were different it will be 1 or odd number of 1-bits we repeat this again with 1/4 of size and so on till we reach 8 at last we can AND our word with 0XFF to set everything but last 8 bits to zero then we use table

// 32 bit word
unsigned int v;
v ^= v >> 16;
v ^= v >> 8;
 
bool parity = ParityTable256[v & 0xff];

Another way to break them down is casting them to unsigned char array and XOR all the bytes at each step the next byte stores the evenness or oddness of 1-bits then we can use table

// 32 bit word
unsigned int v;
unsigned char* p = (unsigned char *) &v;
parity = ParityTable256[p[0] ^ p[1] ^ p[2] ^ p[3]]

at each point we get XOR of original and folded version so that

flip §

flip bits to the right of nth bit

unsigned int v;
short int n;
v = v & ((1<<n)-1) 

set bit §

set to 0 -> AND 0 set to 1 -> OR 1 flip -> XOR 1

complements §

encode symmetric sets of pos,neg ints so they can use the same addition algorithms method 1-> (A - B) -> ~(~A + B) method 2-> (A - B) -> (A + ~B) -> drop leading 1 -> subtract 1 ex: 9’s complement 999, A=472, B=215, ~A=527, ~B=784, A-B = 257 method 1-> ~(527+215) = ~742 = 257 method 2-> (472 + 784) = 1256 -> drop 1-> 256 -> add 1 -> 257

two’s complement of n-bit number -> complement of number wrt 2^n two’s complement -> 3 bits 000 -> 0 001 to 011 -> 1 to 3 100 to 111 -> -4 to -1