Title: Theory / Unimportant / CS / Algo / Hacker's delight{ / 02 Basics
Tags: fromMath mathToDef descriptionToNotation toBinary expressionButNoExpression2 check todo

Page: 11
Variables: \(x\) a binary number.
Expression: \(x\&(x-1)\)
Chapter: 2
Section: 1
Binary: Turn off the rightmost 1-bit if \(x\ne 0\), \(0\) otherwise

Page: 11
Variables: \(x\) a binary number.
Expression: \(x\&(x-1)=0\)
Chapter: 2
Section: 1
Numeric: \(x\in\{0\}\cup\{2^i\mid i\in \mathbb N\}\)

Page: 11
Variables: \(x\) a binary number.
Expression: \(x\&(x+1)=0\)
Chapter: 2
Section: 1
Numeric: \(x\in\{2^{i}-1\mid i\in \mathbb N\}\)

Page: 11 not in the book
Variables: \(x\) a binary integer.
Expression: \(x\oplus(x-1)\)
Chapter: 2
Section: 1
Binary: Mask that idenfies the right-most 1 bit and the trailing 0's
Expression2: \(x\equiv-x\)

Page: 12
Variables: \(x\) a binary integer.
Expression: \(x|(x-1)\)
Chapter: 2
Section: 1
Binary: Propagate the right-most 1 bit to the right, if \(x\ne0\)
all-1 otherwise

Page: 12
Variables: \(x\) a binary integer.
Expression: \(((x|(x-1))+1)\)
Chapter: 2
Section: 1
Binary: Turn-of the right-most string of 1-bit, write a 1 on its left
Explanation: propagate the right most 1 bit, turn those 1 into 0 (creating a new one) to their left

Page: 12
Variables: \(x\) a binary integer.
Expression: \(((x|(x-1))+1)\&x\)
Chapter: 2
Section: 1
Binary: Turn-off the right-most string of 1-bit
Explanation: Turn-on the 0s on the right if any. y=x|(x-1)
Turn off the 1s of the right (the one just turned on and the one already present) (y+1)&x

Smaller0: implemented with word-parallel add, subtract, and, or, not
Greater0: each bit of the result of \(f\) depends only on bits at and to the right of each inpupt operand
Page: 12
Chapter: 2
Section: 1
Variables: \(f\) a \(2^{32}\to2^{32}\) function
Kind: Theorem
Smaller to greater: iff
Prefix Smaller: \(f\) can be

Page: 15
Variables: \(x\) a binary integer.
Expression: \(\neg x+1\)
Chapter: 2
Binary: Inverse each bit, except the right-most 1, and the ones on its right
Expression2: \(-x\)
Expression3: \(\neg(x-1)\)

Page: 15
Variables: \(x\) a binary integer.
Chapter: 2
Binary: not x
Notation: \(\neg x\)
Numeric: \(-x-1\)

Question: \(x-\neg y-1\)
Answer: \(x+y\)
Page: 15
Chapter: 2
Variables: \(x,y\) a binary integer.

Question: \((x\oplus y)+2(x\&y)\)
Answer: \(x+y\)
Page: 15
Chapter: 2
Variables: \(x\), \(y\) binary integer

Question: \((x| y)+(x\&y)\)
Answer: \(x+y\)
Page: 15
Chapter: 2
Variables: \(x,y\) a binary integer.

Question: \(2(x| y)-(x\oplus y)\)
Answer: \(x+y\)
Page: 15
Chapter: 2
Variables: \(x,y\) a binary integer.

Page: 15
Variables: \(x,y\) a binary integer.
Expression: \((x|y)-(x\& y)\)
Chapter: 2
Binary: (bitwise xor)
Notation: \(x\oplus y\)

Page: 15
Variables: \(x,y\) binary integers.
Expression: \((x\&y)-(x|y)-1\)
Chapter: 2
Binary: Bitwise equivalence
Notation: \(x\equiv y\)
Expression2: \((x\&y)+\neg(x|y)\)

Page: 15
Variables: \(x,y\) a binary integer.
Expression: \((x\&\neg y)+y\).
Chapter: 2
Binary: Bitwise or
Notation: \(x|y\)
Explanation: Either it belongs to \(y\). Or it does not belong to \(y\), but to \(x\)

Question: \((\neg x|y)\) equals
Answer: \(x\implies y\)
Page: 15
Chapter: 2
Variables: \(x,y\) a binary integer.

Question: \((\neg x|y)-\neg x\) equals
Answer: \(x\&y\)
Page: 15
Chapter: 2
Variables: \(x,y\) a binary integer.
Extra: It belongs to \(x\mapsto y\) and to \(x\)

Smaller0: \(\text{max}(x,y)\)
Greater0: \((x|y)\)
Page: 15
Chapter: 2
Variables: \(x,y\) a binary integer.
Smaller to greater: \(\stackrel u\le\)
Greater to smaller: \(\stackrel u\ge\)

Smaller0: \((x\&y)\)
Greater0: \(\text{min}(x,y)\)
Page: 15
Chapter: 2
Variables: \(x,y\) a binary integer.
Smaller to greater: \(\stackrel u\le\)
Greater to smaller: \(\stackrel u\ge\)

Smaller0: \(|x-y|\)
Greater0: \((x\oplus y)\)
Page: 17
Chapter: 2
Section: 3
Variables: \(x,y\) a binary integer.
Index: e
Smaller to greater: \(\stackrel u\le\)
Greater to smaller: \(\stackrel u\ge\)

Smaller0: \((x|y)\)
Greater0: \((x+y)\)
Page: 17
Chapter: 2
Section: 3
Variables: \(x,y\) a binary integer.
Index: c,d
Smaller to greater: \(\stackrel u\le\)
Assuming: the addition does not overflow
Greater to smaller: \(\stackrel u\ge\)

Smaller0: \((x+y)\)
Greater0: \((x|y)\)
Page: 17
Chapter: 2
Section: 3
Variables: \(x,y\) a binary integer.
Index: c,d
Smaller to greater: \(\stackrel u<\)
Assuming: The addition overflows
Greater to smaller: \(\stackrel u>\)

Page: 22
Variables: \(x,y\) binary integers.
Expression: \((x|\neg y)\&((x\oplus y)|\neg(y-x))\),
Chapter: 2
Section: 11
Notation: \(x\stackrel{s}\le y\)
Expression2: \(((x\equiv y)\stackrel{s}{>>}1)+(x\&\neg y)\)
Explanation: (forbid «x non negative and y negative»)&((if distinct sign accept)|(implictly assume same sign, hence no overflow: is y ge 0 ?))
Explanation2: ???

Page: 22
Variables: \(x,y\) binary integers.
Expression: \((\neg x\&y)|((x\equiv y)\&(x-y))\)
\((\neg x\&y)|((\neg x|y)\&(x-y))\),
Chapter: 2
Section: 11
Notation: \(x\stackrel{u}{<} y\)
Expression2: \(\left[\left(x\stackrel{u}{>>}1\right)-\left(y\stackrel{u}{>>}1\right)\right]-\left(\neg x\&y\&1\right)\)
Explanation: Either \(x<2^{31}, y\ge 2^{31}\) or \(x-y\) and the difference is at most \(2^{31}\), so no overflow
Explanation2: --if \(x>y+1\) then the equation is \([n]-m\) with \(n>0\) and \(m\in\{0,1\}\)
--if \(x=y+1\) then the equation is either \([0]-0\) or \([1]-(-1)\)
--if \(x=y\) then the equation is [0]-0
--if \(x=y-1\) then the equation is either \([0]-1\) or \([-1]-0\)
--if \(x<y-1\) then the equation is \([n]-m\) with \(n<0\) and \(m\in\{0,1\}\)

Page: Not in the book
Variables: \(x\) a binary number.
Expression: \(x+1\)
Binary: Transform the right most 0 into 1, and the 1s on its right into 0s
Expression2: \(-(\neg x)\)

Page: Not in the book
Variables: \(x\) a binary number.
Expression: \(x-1\)
Binary: Transform the right most 1 into 0, and the 0s on its right into 1s
Expression2: \(\neg(-x)\)

Page: Not in the book
Variables: \(x\) a binary number.
Expression: \(-x\)
Binary: Inverse all bits on the left of the right-most 1

Page: 21
Variables: \(x\in\mathbb Z\) a binary number in 32 or 64 bits.
Chapter: 2
Section: 11
Abbreviation: nlz
Name: Number of leading zero

Page: 21
Variables: \(x\in\mathbb Z\) a binary number
Chapter: 2
Section: 11
Notation: nabs(\(x\))
Numeric: -abs(\(x\))

Page: 37
Variables: \(x,y\in\mathbb Z\) binary numbers.
Expression: \(\max(x-y,0)\).
Chapter: 2
Section: 11
Abbreviation: doz(\(x,y\))
Name: difference or zero

Page: 19
Variables: \(x\in\mathbb Z\) a 32-bit binary number
Expression: \((x\stackrel{s}{>>}31)|(-x\stackrel{u}{>>}31)\)
Chapter: 2
Section: 7
Binary: If \(x<0\), then all 1.
If \(x>0\) all 0 except the rightmost, the right is 1.
If \(x=0\), all 0.
Expression2: \(-(x\stackrel{u}{>>}31)-((-x)\stackrel{u}{>>}31)\)
Numeric: [$]x\mapsto \begin{cases} -1&\qif x<0\\0&\qif x=0\\1&\qif x>0\end{cases}[/$]
Explanation2: If \(x\ne-2^{31}\). If \(x<0\) then \(-(1)-0\), if \(x>0\) then \(-(0)-(1)\), and if \(x=0\), then \(-(0)-(0)\).
Expression3: \((x>0)-(x<0)\), \((x\ge0)-(x\le0)\)
Explanation4: -1 if \(x<0\), 0 if \(x=0\) and \(1\) if \(x>0\)
Abbreviation: \(\text{sign}(x)\)
Name: Sign function

Page: 19, 20
Variables: \(x,y\in\mathbb Z\) 32 bit binary numbers.
Expression: \(\text{sign}(x-y)\)
Chapter: 2
Section: 8
Notation: \(\text{cmp}(x,y)\)
Expression2: \((x>y)-(x<y)\),
\((x\ge y)-(x\le y)\)
Numeric: Three-valued compare function

Page: 20
Variables: \(x,y\in\mathbb Z\) a 32-bit binary number.
Expression: \(t\leftarrow y\stackrel{s}{>>} 31\), \((\text{abs}(x)\oplus t)-t \),\(t\leftarrow y\stackrel{s}{>>} 31\), \((\text{abs}(x)+ t)\oplus t \),
Chapter: 2
Section: 9
Binary: Transfer of sign from \(y\) to \(x\)
Notation: ISIGN\((x,y)\)
Expression2: \(t\leftarrow (x\oplus y)\stackrel{s}{>>} 31\), \((x\oplus t)-t \),\(t\leftarrow (x\oplus y)\stackrel{s}{>>} 31\), \((x+t)\oplus t\).
Numeric: \(\text{abs}(x)\) if \(y\ge0\) and \(-\text{abs}(x)\) otherwise.
That is: \((-\text{abs}(x)-1)-(-1)\) if \(y<0\), \(\text{abs}(x)\) otherwise
Explanation: That is: \((-x-1)-(-1)\) if \(x\) and \(y\)'s sign are distinct
That is: \(-(x-1)-1\) if \(x\) and \(y\)'s sign are distinct
Explanation2: That is: \(-(\text{abs}(x)-1)-1\) if \(y<0\), \(\text{abs}(x)\) otherwise

Page: 23
Variables: \(x\in\mathbb Z\) a 32-bit binary number
Expression: \(\text{nabs}(x)\)
Chapter: 2
Section: 11
Notation: \(x\ne0\)
Expression2: \(\text{nlz}(x)-32\)
Explanation: Sends 0 to 0, everything else to negative number
Explanation2: 0 is the only value such that \(\text{nlz}(x)\ge 32\), therefore, it sends \(0\) to 0 and everything else to negative value
Expression3: \(x|-x\)
Expression4: \((x\stackrel{u}{>>}1)-x\)
Explanation3: 0|0, otherwise one is negative, so sign bit of the or is negative
Explanation4: sends 0 to 0, positive to \(-\frac x2\), hence negative. Sends negative to \(\lfloor\frac x{2}\rfloor+2^{31}-x=-\frac x2+2^31\)

Page: 23
Variables: \(x\in\mathbb Z\) a 32-bit binary number
Expression: -\(x\)
Chapter: 2
Section: 11
Notation: \(x<0\)
Context: Answer in the left-most bit

Page: 23 2nd not in the book
Variables: \(x\in\mathbb Z\) a 32-bit binary number
Expression: \(x|(x-1)\)
Chapter: 2
Section: 11
Notation: \(x\le 0\)
Expression2: \((x/2)-1\)

Page: 23
Variables: \(x\in\mathbb Z\) a 32-bit binary number
Expression: -\(\neg x\)
Chapter: 2
Section: 11
Notation: \(x\ge 0\)
Context: Answer in first bit

Page: 23
Variables: \(x\in\mathbb Z\) a 32-bit binary number.
Expression: \(x\oplus\text{nabs}(x)\)
Chapter: 2
Section: 11
Notation: \(x>0\)
Expression2: \(-\lceil x/2\rceil\)
Explanation: The sign bit is distinct in both part only when \(x>0\)
Explanation2: equivalent to \((x/2)-x\), which is positive/negative iff \(x\) is negative/positive
Expression3: \(-x\&\neg x\)
Explanation3: Sign bit to 1 if (\(-x<1\), i.e. \(0<x<2^{32}-1\)) and (\(\neg x<0\), hence \(x\ge0\)).

Page: 23
Variables: \(x\in\mathbb Z\) a 32-bit binary number
Expression: \(x\)
Chapter: 2
Section: 11
Notation: \(x<0\)
Context: Answer in first bit

Page: Not in the book
Variables: \(x\) a 32 bit integer
Expression: \(x\stackrel{s}{>>}31\).
Numeric: -1 on negative, 0 otherwise

Page: Not in the book
Variables: \(x\) a 32 bit integer
Expression: \(x\oplus (x\stackrel{s}{>>} 31)\).
Numeric: \(\neg x\) if \(x<0\), \(x\) otherwise
Explanation: \(x\oplus (\text{-1 on negative, 0 otherwise})\)

Page: Not in the book
Variables: \(x,y\) be binary integers
Expression: \(\neg(x|y)\).
Notation: \(x\downarrow y\)
Numeric: \(x\) nor \(y\)

Page: Not in the book
Variables: \(x,y\) be binary integers
Expression: \(\neg(x\&y)\).
Notation: \(x\uparrow y\)
Numeric: \(x\) nand \(y\)

Page: Not in the book
Variables: \(x\) a 32 bits binary integer
Expression: \(x\stackrel{u}{>>}31\).
Numeric: \(0\) if \(x\ge 0\), \(1\) otherwise

Page: 18
Variables: \(0\le n<32\) int
Expression: \(0x8000 000\stackrel{u}{>>}(31-n)\)
Chapter: 1
Section: 6
Binary: The \(n\)-th bit to one
Notation: \(2^n\)
Expression2: \(1<<n\)

Page: 18
Variables: \(x\) a 32-bit binary variables
\(n\) a variables between \(0\) and \(31\)
Expression: \(\left(x\stackrel{s}{>>}31\right)<<32-n\).
Chapter: 1
Section: 6
Binary: The \(n\)-leftmost bits are the sign bit of \(x\),
The \(32-n\)-rightmost bits are 0

Page: Not in the book
Variables: \(n\) a variables between \(0\) and \(32\)
Expression: \(-1\stackrel{u}{>>}(32-n)\)
Binary: \(32-n\) bits to 0, \(n\) bits to 1
Notation: \(2^n-1\)
Expression2: \(\big(1<<(n+1)\big)-1\)

Page: Not in the book
Variables: \(n\) a variables between \(0\) and \(32\)
Expression: \(-1{<<}n\),
Binary: \(32-n\) 1's, \(n\) 0's
Notation: \(-2^n\) if \(n<31\), \(0\) if \(n=31\)
Expression2: \(0x8000 000\stackrel{s}{>>}(31-n)\)

Page: Not in the book
Variables: \(n\) a variables between \(0\) and \(32\)
Expression: \(-1\oplus (1<<n)\),
Binary: \(n\)-th bit is 0, everything else is 1
Expression2: \((-1<n)-1\)
Numeric: \(-2^{n}-1\) if \(n<32\), \(2 ^{32}-1\) if \(n=32\)
Expression3: \(-1-(1<<n)\)

Page: not in the book
Variables: \(x\) a signed 32-bit variable,
\(0<n<32\)
Expression: Sends non-negative to \(\lfloor\frac x{2^n}\rfloor\) and negative to \(\lfloor\frac x{2^n}\rfloor+2^{32-n}\).
Chapter: 2
Notation: \(x\stackrel{u}{>>}n\)
Property: Increasing on non-negative, from \(0\) to \(2^{32-n}-1\),
Increasing on negative from \(2^{32-n}\) to \(2^{32-n+1}-1\).

Page: Not in the book
Expression: \(-(x\&1)\)
Binary: propagate 0th(right-most) bit
Expression2: \((x<<31)\stackrel{s}{>>}31\)

Page: 11 Last not in book
Variables: \(x\) a binary integer.
Expression: \(x\uparrow(x-1)\)
Chapter: 2
Section: 1
Binary: Mask that idenfies the trailing 0's
Expression2: \(x\downarrow (-x)\)
Explanation: The right most one becomes a 0 in \(\neg x\), every bits on its left are 0 in one of the two sides.
Explanation2: The bits which are not (at the left of a 1, or a 1)
Expression3: \((x\&(-x))-1\)
Expression4: \((x-1)\&(\neg x)\)
Explanation3: i.e. isolate the right-most one, transform it into 0 and the 0 on their right into 1.

Page: 22
Variables: \(x,y\) a binary integer.
Expression: \((x-y)\oplus\Big((x\oplus y)\&\big((x-y)\oplus x\big)\Big)\)
Chapter: 2
Section: 11
Notation: \(x<y\)
Expression2: \((x\&\neg y)|\big((x\equiv y)\&(x-y)\big)\)
Explanation: ???
Explanation2: Either \(x<0\land y\ge0\) or (both have same sign and \(x<y\))
Expression3: \(nabs(doz(y,x))\)
Expression4: \(\Big(\left(x\stackrel{s}{>>}1\right)-\left(y\stackrel{s}{>>}1\right)\Big)-(\neg x\& y\&1)\)
Explanation3: doz is 0 if \(x\ge y\) and positive if \(x<y\). nabs is \(0\) if \(x\ge y\) and negative if \(x<y\).
Explanation4: --if \(x>y+1\) then the equation is \([n]-m\) with \(n>0\) and \(m\in\{0,1\}\)
--if \(x=y+1\) then the equation is either \([0]-0\) or \([1]-(-1)\)
--if \(x=y\) then the equation is [0]-0
--if \(x=y-1\) then the equation is either \([0]-1\) or \([-1]-0\)
--if \(x<y-1\) then the equation is \([n]-m\) with \(n<0\) and \(m\in\{0,1\}\)

Page: 22
Variables: \(x,y\in\mathbb Z\) a 32-bit binary number.
Expression: \((\neg x|y)\&((x\oplus y)|\neg(y-x))\).
Chapter: 2
Section: 11
Notation: \(x\stackrel{u}\le y\)
Explanation: (\(x\ge0\) or \(y<0\)) and (either they have distinct sign, or (assuming they have the same sign; \(x\le y\).))

Page: 23
Variables: \(x\in\mathbb Z\) a 32-bit binary number
Expression: \(\text{abs}(x)-1\)
Chapter: 2
Section: 11
Notation: \(x=0\)
Expression2: \(\text{abs}(x+0x8000 000)\)
Numeric: sends 0 to -1, everything else to positive
Explanation: 0x8000 000 is its own absolute. every other absolute are positive
Expression3: \(\text{nlz}(x)<<26\)
Expression4: \(-(\text{nlz}(x)\stackrel{u}{>>}5)\)
Explanation3: The 5th bit of \(\text{nlz}(x)\) is 1 iff \(x=0\) (hence \(\text{nlz}(x)\) is at least 32, which is the maximal value). This bit is then moved to the sign bit.
Explanation4: \(\text{nlz}(x)\) is a positive number, at most 32. Divided by 32 (\(\stackrel u{>>}5\)) lead to either 0 if \(x=0\), or 1 otherwise. Hence the result is \(0\) if \(x=0\) and \(-1\) otherwise.
Expression5: \(\neg(x\ne 0)\)
Expression6: \(\neg x\& (x-1)\)
Explanation6: if \(0\), it is \(-1\&-1\), otherwise one of the number is positive, thus the sign bit of the result is 0.

Page: 18
Variables: \(y\) a binary integer of length 32
\(0\le n\le 31\)
Expression: \(((y+0x8000 000)\stackrel{u}{>>}n)-(0x8000 000\stackrel{u}{>>}n))\).
Chapter: 2
Section: 6
Binary: Shift right signed, using unsigned. \(y\stackrel{s}{>>}n\)
Expression2: \(t\leftarrow 0x8000 0000\stackrel{u}{>>}n\); \(((y\stackrel{u}{>>}n)\oplus t)-t\)
Explanation: If \(y<0\), then the leading 1 is switched to 0. The substraction then transform back this 0 in 1, and all preceding 1 into 0 thanks to the carry. Otherwise, if \(y\ge 0\), then the sign 0 is switched to 1, the shift is done, and the 1 is shifted back to 0 without carry
Explanation2: Same than the preceding one. Shift before switching
Expression3: \(t\leftarrow (y\,\&\,0x8000 000)\stackrel{u}{>>}n\); \((y\stackrel{u}{>>}n)-(t+t)\)
Expression4: \(\left(y\stackrel{u}{>>}n\right)|\Bigg(\Big(-\left(y\stackrel{u}{>>}31\right)\Big)\stackrel{u}{<<}(31-n)\Bigg)\)
Explanation3: ???
Explanation4: The left part sets the \(32-n\) rightmost bits. The right part sets the \(n\) leftmost bit: indeed \(-\left(y\stackrel{u}{>>}31\right)\) is -1 if \(y<0\) and \(0\) otherwise,
Expression5: \(t\leftarrow -(y\stackrel{u}{>>}31)\); \(((y\oplus t)\stackrel{u}{>>}n)\oplus t\)
Explanation5: \(t\) is \(y\stackrel{s}{>>}31\), hence \(-1\) if \(y<0\), \(0\) if \(y\ge 0\). Hence \(\neg(\neg x\stackrel{u}{>>}n)\) if \(y<0\), and \(y\stackrel{u}{>>}n\) if \(y\ge0\)

Page: 17
Variables: \(x\) a binary integer.
Expression: \((2x\& x\stackrel{s}{>>} 31)\).
Chapter: 2
Section: 4
Numeric: \(2x\) if \(x<y\),
\(0\) otherwise

Page: 17
Variables: \(x\) a binary integer.
Expression: \(x-(2x\& y)\).
Chapter: 2
Section: 4
Expression2: \((x\oplus y)-y\),
Numeric: Absolute value of \(x\)
Explanation: \((-x-1)-(-1)\) if \(x<0\)
Explanation2: \(- (-x-1)-1\) if \(x<0\)
Expression3: \((x+y)\oplus y\)
Explanation3: \(x-2x\) if \(x<0\)

Page: 17
Variables: \(x\) a binary integer.
Expression: \(x\oplus\left(x\stackrel{s}{>>}31\right)\),
Chapter: 2
Section: 4
Numeric: \(\neg x\) if \(x<0\),
\(x\) otherwise

Page: 17
Variables: \(x\) a binary integer.
Expression: \(x+\left(x\stackrel{s}{>>} 31\right)\)
Chapter: 2
Section: 4
Numeric: \(x-1\) if \(x<0\),
\(x\) otherwise

Page: 11
Variables: \(x\) a binary integer.
Expression: -\(\neg x\& (x+1)\)
Chapter: 2
Section: 1
Binary: Isolate the rigthmost 0 bit if \(x\ne 2^{32}-1\), \(0\) otherwise
Explanation: Every element left to a 0 are 0 either in \(\neg x\) or in \(x+1\). The (potentially empty) sequence of 1 on the right is turned to 0 in the right part. The right most 0 is turned into 1 in both side.

Page: 11
Variables: \(x\) a binary number.
Expression: \(x\& (-x)\)
Binary: Isolate the rigthmost 1 if \(x\ne 0\), \(0\) otherwise