Title: Theory / Unimportant / CS / Algo / Hacker's delight{ / 03 Power of 2 boundaries
Tags: fromMath descriptionToNotation récupéré

Page: 45
Variables: \(n\in\mathbb N\)
\(x\) a binary number, signed or unsigned
Expression: \(x\& -2^n\)
-\(x\&((-1)<<n)\)
Chapter: 3
Section: 1
Expression2: \((x\stackrel{u}{>>}n)<<n\)
Numeric: Rounding down to the greatest multiple of \(2^n\) less than \(x\)
Explanation: -\(-2^n\) have \((32-n)\) 1 and \(n\) 0. Thus, the \(n\) right most digit are 0ed
-\((-1)<<n\) is equal to \(-2^n\)
Explanation2: moving to right and then left cancel the \(n\) right most 0

Page: 45
Variables: \(n\in\mathbb N\)
\(x\) a binary number
Expression: \(\left(x +(2^n-1)\right)\& -2^n\).
Chapter: 3
Section: 1
Expression2: \(t\leftarrow (-1)<<n\), \((x-t-1)\&t\)
Numeric: Rounding up to the least multiple of \(2^n\) greater than \(x\)
Explanation: Rounding down to the greatest multiple of \(2^n\) greater than \(x +(2^n-1)\)
Explanation2: \(t=2^n-1\), hence rounding down to the greatest multiple of \(2^n\) greater than \(x+(2^n-1)\)
Expression3: \(t\leftarrow(1<<n)-1\), \((x+t)\&\neg t\).
Expression4: \(x +\left((-x)\& \left(2^n-1\right)\right)\).
Explanation3: Let \(m\) maximal such that \(2^m|x\); then \(x\) plus (the inverse of \(x\) in the \(n\) least bits plus \(2^m\))
Explanation4: \(t\) is \(-2^n\); then \(x+2^n-1\) with its \(n\) first bits at 0.

Page: 45
Variables: \(n\in\mathbb N\)
\(x\) a 32-bit signed binary number
Expression: \(\bigg( x+\big(x\stackrel{s}{>>} 31\big)\&\big(2^n-1\big)\bigg)\& \big(-2^n\big)\).
Chapter: 3
Section: 1
Expression2: \(\bigg(x+\Big(\big(x\stackrel{s}{>>} (n-1)\big)\stackrel{u}{>>}(32-n)\Big)\bigg)\&\big(-2^n\big)\).
Numeric: Rounding a signed integer to the multiple of \(2^n\) toward 0
Explanation: if \(x\ge0\): the formula for greatest multiple of \(2^n\) smaller than \(x\), otherwise the formula for the least multiple greater than \(x\) (i.e. \((x+(2^n-1))\&(-2^n)\)).
Explanation2: if \(x\ge 0\): the formula for greatest multiple. Otherwise the formula for least multiple, (i.e. \((x+(2^n-1))\&(-2^n)\)).

Smaller0: flp2(\(x\))
Greater0: clp2(\(x\))
Page: 46
Chapter: 3
Section: 2
Variables: \(n\in\mathbb N\)
\(x\ge 0\)
Smaller to greater: =
Assuming: \(x\) is a power of 2, or 0
Extra: plusieurs solution

Smaller0: flp2(\(2^nx\))
Greater0: \(2^n\)flp2(\(x\))
Page: 46
Chapter: 3
Section: 2
Variables: \(n\in\mathbb Z\)
\(x\ge 0\)
Smaller to greater: =
Hide middle: yes

Smaller0: \(\text{clp}2(1/x)\)
Greater0: \(\frac{1}{\text{flp}2(x)} \)
Page: 46
Chapter: 3
Section: 2
Variables: \(n\in\mathbb Z\)
\(x> 0\)
Smaller to greater: =
Hide middle: yes

Page: 46, 47, 48
Variables: \(n\in\mathbb N\) and
\(x\ge 0\)
Expression: \(1<<(32-\text{nlz}(x-1))\).
Chapter: 3
Section: 2
Notation: clp2(\(x\))
Expression2: \(0x8000 000\stackrel{u}{>>}\text{nlz}(x-1)-1\)
Numeric: The least power of \(2\) greater than \(x\), sending 0 to 0
Expression3: \(\text{2flp2}(x-1)\) if \(x\ne 1\).
Expression4: \(\text{flp2}(2x-1)\stackrel{u}/2\) if \(1\le x\le 2^{31}\).
Expression5: --\(x=x-1\);
--\(x=x|x>>1\);
--\(x=x|x>>2\);
--\(x=x|x>>4\);
--\(x=x|x>>8\);
--\(x=x|x>>16\);
--return \(x+1\);
Expression6: \(2\text{flp2}(x-1)\) if \(x\ne 1\)

Page: 49, 50
Variables: \(a\) unsigned integers,
\(n\in\mathbb N\)
Expression: \((a|-2^n)\),
Chapter: 3
Notation: \(\left[-2^n,-1\right]\cap a+2^n\mathbb Z\)
Explanation: the bit of a, and the bit after the \(n\)-th one, hence \([-2^n,-1]\cap a+2^n\mathbb Z\)

Name: Test whether, from \(a\) to \(a+l\), no boundary of block of size \(2^n\) is crossed
Definition: \(a/(2^n)=(a+l)/(2^n)\).
Page: 49, 50
Chapter: 3
Variables: \(a,l\) unsigned integers,
\(n\in\mathbb N\)
Definition2: \(\left([0,2^n-1]\cap a+2^n\mathbb Z\right)\stackrel u< l\).
Conjdef: Assuming that \(a+l\) is computed modulo some number, the first solution can't be used
Extra: 1-Whether a block of size \(2^n\) of \(a\) is the same as the one of \(a+l\)

Page: 49, 50
Variables: \(a\) unsigned integers,
\(n\in\mathbb N\)
Expression: \(\Big(a\&\left(2^n-1\right)\Big)\).
Chapter: 3
Notation: \([0,2^n-1]\cap a+2^n\mathbb Z\)
Explanation: \(a\&\left(2^n-1\right)\) is \([0,2^n-1]\cap a+2^n\mathbb Z\), hence \(2^n-\left(a\&\left(2^n-1\right)\right)\) is \([1,2^n]\cap -a+2^n\mathbb Z\), it does not crosses a boundary if this number is less than \(l\)

Page: 49, 50
Variables: \(a\) unsigned integers,
\(n\in\mathbb N\)
Expression: \(-(a|-2^n)\)
Chapter: 3
Expression2: \(2^n-\left(a\&\left(2^n-1\right)\right)\)
Numeric: \(\left[1,2^n\right]\cap -a+2^n\mathbb Z\)
Explanation: \(-\Big(\left[2^n,-1\right]\cap a+2^n\mathbb Z\Big)\)
Explanation2: \(2^n-\Big(\left[0,2^n-1\right]\cap a+2^n\mathbb Z\Big)\)

Page: 46, 47, 48
Variables: \(n\in\mathbb N\) and
\(x\ge 0\) unsigned int
Expression: \(1<<(31-\text{nlz}(x))\), assuming \(1<<-1=0\).
Chapter: 3
Section: 2
Binary: switching all to 1 but left most 1
Notation: flp2(\(x\))
Expression2: \(1<<(31\oplus \text{nlz}(x))\).
Numeric: The greatest power of \(2\) less than \(x\)
Expression3: \(\text{clp2}(x\stackrel{u}/2+1)\) if \(x\ne 0\)
\(\text{clp2}(x+1)\stackrel{u}/2\) if \(x<2^{31}\).
Expression4: \(0x8000 000\stackrel{u}{>>}\text{nlz}(x)\).
Expression5: {-\(x=x|x>>1\);
--\(x=x|x>>2\);
--\(x=x|x>>4\);
--\(x=x|x>>8\);
--\(x=x|x>>16\);
--return \(x -(x>>1)\);}
Expression6: {-\(y=0x8000 000\);
--while(y>x) y=y>>1;
--return y;