<commit_before>---
layout: post
categories: [cheatsheet]
share: true
comments: true
title: 'Bits, bitmasks and bit manipulations'
excerpt: 'Bit manipulation cheat sheet'
date: '2016-01-12T15:15:00+01:00'
tags: [coding]
author: maze
hidelogo: true
hidden: false
mathjax: true
---

# Contents

*  Contents
{:toc}

# Terminology {#terminology}

| Term                        | Bits     | Bytes    | [NASM][] | [GAS][]
|:--------------------------- |:---------|:---------|:---------|:-----------
| *nibble*                    | 4 bits   | ½ byte   |          |
| *byte*                      | 8 bits   | 1 byte   | `DB`     | `.byte`
| *word*                      | 16 bits  | 2 byte   | `DW`     | `.word`
| *dword* or *double word*    | 32 bits  | 4 bytes  | `DD`     | `.long`
| *qword* or *quad word*      | 64 bits  | 8 bytes  | `DQ`     |
| *tword* or *ten word*       | 80 bits  | 10 bytes | `DT`     |
| *oword* or *octo word*      | 128 bits | 16 bytes | `DO`     |
| *yword* <sup>1</sup>        | 256 bits | 32 bytes | `DY`     |
| *zword* <sup>2</sup>        | 512 bits | 64 bytes | `DZ`     |

1.  Intel [AVX](https://en.wikipedia.org/wiki/Advanced_Vector_Extensions) `YMM` register
2.  Intel [AVX-512](https://en.wikipedia.org/wiki/AVX-512) `ZZM` register

[GAS]: http://tigcc.ticalc.org/doc/gnuasm.html
[NASM]: http://www.nasm.us

# Binary {#binary}

Binary numbers, or *bits* are numbers in the *base-2* number system. "Orinary"
numbers are in *base-10*, hexadecimal numbers are in *base-16*:

{% highlight c %}
/* base-10 */
2342     = 2 * (10 ** 3) + 3 * (10 ** 2) + 4 * (10 ** 1) + 2 * (10 ** 0)  = 2342;
/* base-16 */
0x172a   = 1 * (16 ** 3) + 7 * (16 ** 2) + 2 * (16 ** 1) + 10 * (16 ** 0) = 2342;
/* base-2 */
0b101010 = 1 * ( 2 ** 5) + 1 * ( 2 ** 3) + 1 * ( 2 ** 1)                  =   42;
{% endhighlight %}

# Nibbles {#nibbles}

A byte consists of two nibbles, or *half bytes*. A nibble contains 4 bits of
information, thus an 8 bit byte contains two nibbles.

{% highlight c %}
/*
0x0 = 0000 ; 0x4 = 0100 ; 0x8 = 1000 ; 0xc = 1100
0x1 = 0001 ; 0x5 = 0101 ; 0x9 = 1001 ; 0xd = 1101
0x2 = 0010 ; 0x6 = 0110 ; 0xa = 1010 ; 0xe = 1110
0x3 = 0011 ; 0x7 = 0111 ; 0xb = 1011 ; 0xf = 1111
*/

uint8_t msn, lsn;
/*  most significant nibble: */   msn = (x & 0xf0) >> 4;
/* least significant nibble: */   lsn = (x & 0x0f);
/*          nibbles to byte: */     x = (msn << 4) | lsn;
{% endhighlight %}

# Bit operations {#bit-operations}

{% highlight c %}
uint8_t x, y;
/*   get bit y in x: */            x &=  (1 << y);
/*   set bit y in x: */            x |=  (1 << y);  
/* unset bit y in x: */            x &= ~(1 << y);  
{% endhighlight %}

## Bit masks {#bit-masks}

{% highlight c %}
#define FEATURE_NONE    (0x00)
#define FEATURE_A       (1 << 0)
#define FEATURE_B       (1 << 1)
#define FEATURE_C       (1 << 2)
#define FEATURE_D       (1 << 3)
#define FEATURE_E       (1 << 4)
#define FEATURE_F       (1 << 5)
#define FEATURE_G       (1 << 6)
#define FEATURE_H       (1 << 7)
#define FEATURE_ALL     (0xff)

uint8_t features = FEATURE_NONE;

void enable_feature(uint8_t feature) {
    features |= feature;
}

void disable_feature(uint8_t feature) {
    features &= ~feature;
}

if (features & FEATURE_B) {
    /* ... */
}
{% endhighlight %}

## Multi byte packing {#multi-byte-packing}

{% highlight c %}
uint8_t a, b, c, d;

/* big endian */
uint16_t  word_be = (a <<  8) | (b      );                         
uint32_t dword_be = (a << 24) | (b << 16) | (c <<  8) | (d      );

/* little endian */
uint16_t  word_be = (a      ) | (b <<  8);                         
uint32_t dword_le = (a      ) | (b <<  8) | (c << 16) | (d << 24);
{% endhighlight %}

## Bit matrix multiplication {#bit-matrix-multiplication}

Given matrices $$ A $$ and $$ B $$:

$$
A = \begin{bmatrix}
1 & 1 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}^{a \times b},
B = \begin{bmatrix}
1 & 0 & 0 \\
1 & 1 & 1 \\
0 & 0 & 1
\end{bmatrix}^{b \times c}
$$

We can calculate $$ A \times B $$ as:

$$
A \times B = \begin{bmatrix}
(1 \land 1) \lor (1 \land 1) \lor (0 \land 0) &
(1 \land 0) \lor (1 \land 1) \lor (0 \land 0) &
(1 \land 0) \lor (1 \land 1) \lor (0 \land 1) \\
(0 \land 1) \lor (1 \land 1) \lor (0 \land 0) &
(0 \land 0) \lor (1 \land 1) \lor (0 \land 0) &
(0 \land 0) \lor (1 \land 1) \lor (0 \land 1) \\
(0 \land 1) \lor (0 \land 1) \lor (1 \land 0) &
(0 \land 0) \lor (0 \land 1) \lor (1 \land 0) &
(0 \land 0) \lor (0 \land 1) \lor (1 \land 1)
\end{bmatrix} = \begin{bmatrix}
1 & 1 & 1 \\
1 & 1 & 1 \\
0 & 0 & 1
\end{bmatrix}^{a \times c}
$$

And for vector $$ \lvert v \rvert $$:

$$
\lvert v \rvert = \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix}
$$

We can calculate $$ A \times \lvert v \rvert $$ as:

$$
A \times \lvert v \rvert = \begin{bmatrix}
(1 \land 0) \lor (1 \land 1) \lor (0 \land 1) &
(0 \land 0) \lor (1 \land 1) \lor (0 \land 1) &
(0 \land 0) \lor (0 \land 1) \lor (1 \land 1)
\end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \end{bmatrix}
$$

# Working with bytes in programming languages {#working-with-bytes-in-programming-languages}

| Language          | Example                                        | Note
|:----------------- |:-----------------------------------------------|:-------------------------------------------------------
| C                 | `uint8_t b = 0x2a; b |= c;`                    | Masking may be required
| Java              | `static byte b = 0x2a; b |= c;`                | Guaranteed to be 8 bit byte
| PHP               | `$b = 0x2a; $b = ($b | $c) & 0xff;`            | No byte type, masking required (depends on size of `c`)
| Python            | `b = bytearray(1); b[0] = 0x2a; b[0] |= c[0];` | Guaranteed to be 8 bit byte
| Ruby              | `b = 0x2a; b = (b | c) & 0xff`                 | No byte type, masking required (depends on size of `c`)<commit_msg>Use programming boolean symbols<commit_after>---
layout: post
categories: [cheatsheet]
share: true
comments: true
title: 'Bits, bitmasks and bit manipulations'
excerpt: 'Bit manipulation cheat sheet'
date: '2016-01-12T15:15:00+01:00'
tags: [coding]
author: maze
hidelogo: true
hidden: false
mathjax: true
---

# Contents

*  Contents
{:toc}

# Terminology {#terminology}

| Term                        | Bits     | Bytes    | [NASM][] | [GAS][]
|:--------------------------- |:---------|:---------|:---------|:-----------
| *nibble*                    | 4 bits   | ½ byte   |          |
| *byte*                      | 8 bits   | 1 byte   | `DB`     | `.byte`
| *word*                      | 16 bits  | 2 byte   | `DW`     | `.word`
| *dword* or *double word*    | 32 bits  | 4 bytes  | `DD`     | `.long`
| *qword* or *quad word*      | 64 bits  | 8 bytes  | `DQ`     |
| *tword* or *ten word*       | 80 bits  | 10 bytes | `DT`     |
| *oword* or *octo word*      | 128 bits | 16 bytes | `DO`     |
| *yword* <sup>1</sup>        | 256 bits | 32 bytes | `DY`     |
| *zword* <sup>2</sup>        | 512 bits | 64 bytes | `DZ`     |

1.  Intel [AVX](https://en.wikipedia.org/wiki/Advanced_Vector_Extensions) `YMM` register
2.  Intel [AVX-512](https://en.wikipedia.org/wiki/AVX-512) `ZZM` register

[GAS]: http://tigcc.ticalc.org/doc/gnuasm.html
[NASM]: http://www.nasm.us

# Binary {#binary}

Binary numbers, or *bits* are numbers in the *base-2* number system. "Orinary"
numbers are in *base-10*, hexadecimal numbers are in *base-16*:

{% highlight c %}
/* base-10 */
2342     = 2 * (10 ** 3) + 3 * (10 ** 2) + 4 * (10 ** 1) + 2 * (10 ** 0)  = 2342;
/* base-16 */
0x172a   = 1 * (16 ** 3) + 7 * (16 ** 2) + 2 * (16 ** 1) + 10 * (16 ** 0) = 2342;
/* base-2 */
0b101010 = 1 * ( 2 ** 5) + 1 * ( 2 ** 3) + 1 * ( 2 ** 1)                  =   42;
{% endhighlight %}

# Nibbles {#nibbles}

A byte consists of two nibbles, or *half bytes*. A nibble contains 4 bits of
information, thus an 8 bit byte contains two nibbles.

{% highlight c %}
/*
0x0 = 0000 ; 0x4 = 0100 ; 0x8 = 1000 ; 0xc = 1100
0x1 = 0001 ; 0x5 = 0101 ; 0x9 = 1001 ; 0xd = 1101
0x2 = 0010 ; 0x6 = 0110 ; 0xa = 1010 ; 0xe = 1110
0x3 = 0011 ; 0x7 = 0111 ; 0xb = 1011 ; 0xf = 1111
*/

uint8_t msn, lsn;
/*  most significant nibble: */   msn = (x & 0xf0) >> 4;
/* least significant nibble: */   lsn = (x & 0x0f);
/*          nibbles to byte: */     x = (msn << 4) | lsn;
{% endhighlight %}

# Bit operations {#bit-operations}

{% highlight c %}
uint8_t x, y;
/*   get bit y in x: */            x &=  (1 << y);
/*   set bit y in x: */            x |=  (1 << y);  
/* unset bit y in x: */            x &= ~(1 << y);  
{% endhighlight %}

## Bit masks {#bit-masks}

{% highlight c %}
#define FEATURE_NONE    (0x00)
#define FEATURE_A       (1 << 0)
#define FEATURE_B       (1 << 1)
#define FEATURE_C       (1 << 2)
#define FEATURE_D       (1 << 3)
#define FEATURE_E       (1 << 4)
#define FEATURE_F       (1 << 5)
#define FEATURE_G       (1 << 6)
#define FEATURE_H       (1 << 7)
#define FEATURE_ALL     (0xff)

uint8_t features = FEATURE_NONE;

void enable_feature(uint8_t feature) {
    features |= feature;
}

void disable_feature(uint8_t feature) {
    features &= ~feature;
}

if (features & FEATURE_B) {
    /* ... */
}
{% endhighlight %}

## Multi byte packing {#multi-byte-packing}

{% highlight c %}
uint8_t a, b, c, d;

/* big endian */
uint16_t  word_be = (a <<  8) | (b      );                         
uint32_t dword_be = (a << 24) | (b << 16) | (c <<  8) | (d      );

/* little endian */
uint16_t  word_be = (a      ) | (b <<  8);                         
uint32_t dword_le = (a      ) | (b <<  8) | (c << 16) | (d << 24);
{% endhighlight %}

## Bit matrix multiplication {#bit-matrix-multiplication}

Given matrices $$ A $$ and $$ B $$:

$$
A = \begin{bmatrix}
1 & 1 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}^{a \times b},
B = \begin{bmatrix}
1 & 0 & 0 \\
1 & 1 & 1 \\
0 & 0 & 1
\end{bmatrix}^{b \times c}
$$

We can calculate $$ A \times B $$ as:

$$
A \times B = \begin{bmatrix}
(1 \& 1) \| (1 \& 1) \| (0 \& 0) &
(1 \& 0) \| (1 \& 1) \| (0 \& 0) &
(1 \& 0) \| (1 \& 1) \| (0 \& 1) \\
(0 \& 1) \| (1 \& 1) \| (0 \& 0) &
(0 \& 0) \| (1 \& 1) \| (0 \& 0) &
(0 \& 0) \| (1 \& 1) \| (0 \& 1) \\
(0 \& 1) \| (0 \& 1) \| (1 \& 0) &
(0 \& 0) \| (0 \& 1) \| (1 \& 0) &
(0 \& 0) \| (0 \& 1) \| (1 \& 1)
\end{bmatrix} = \begin{bmatrix}
1 & 1 & 1 \\
1 & 1 & 1 \\
0 & 0 & 1
\end{bmatrix}^{a \times c}
$$

And for vector $$ \lvert v \rvert $$:

$$
\lvert v \rvert = \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix}
$$

We can calculate $$ A \times \lvert v \rvert $$ as:

$$
A \times \lvert v \rvert = \begin{bmatrix}
(1 \& 0) \| (1 \& 1) \| (0 \& 1) &
(0 \& 0) \| (1 \& 1) \| (0 \& 1) &
(0 \& 0) \| (0 \& 1) \| (1 \& 1)
\end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \end{bmatrix}
$$

# Working with bytes in programming languages {#working-with-bytes-in-programming-languages}

| Language          | Example                                        | Note
|:----------------- |:-----------------------------------------------|:-------------------------------------------------------
| C                 | `uint8_t b = 0x2a; b |= c;`                    | Masking may be required
| Java              | `static byte b = 0x2a; b |= c;`                | Guaranteed to be 8 bit byte
| PHP               | `$b = 0x2a; $b = ($b | $c) & 0xff;`            | No byte type, masking required (depends on size of `c`)
| Python            | `b = bytearray(1); b[0] = 0x2a; b[0] |= c[0];` | Guaranteed to be 8 bit byte
| Ruby              | `b = 0x2a; b = (b | c) & 0xff`                 | No byte type, masking required (depends on size of `c`)
{'fraction_non_alphanumeric': 0.2199582027168234, 'fraction_numerical': 0.07088122605363985, 'mean_word_length': 1.782218992248062, 'pattern_counts': {'":': 0, '<': 91, '<?xml version=': 0, '>': 15, 'https://': 4, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3813878', 'n_tokens_mistral': 5070, 'n_tokens_neox': 4379, 'n_words': 1390}