Title: Theory / Unimportant / CS / Algo / Hacker's delight{ / 04 Arithmetic bounds
Tags: fromAlgorithm hasNotNewEffectReturnsMeaning effectNew instructionToImplementation récupéré keepAlgo

Name: Bound checking
Definition: Checking whether a number \(x\) satisfies \(a\le x\le b\) with \(a,b\) fixed
Page: 51
Chapter: 4
Section: 1
Variables: \(a,b\in\mathbb z\)

Page: 52
Implementation: \(x-a\stackrel{u}\le b-a\)
Section: 1
Chapter: 4
Effect: \(a\le x\le b\)
Variables: \(a,b\) signed or unsigned int
Kind: Theo
Assuming: \(a\le b\)

Smaller0: \(a_1+a_2\ge 2^{32}\) or \(b_1+b_2<2^{32}\) (mathematical addition, without overflow)
Greater0: \([a_1+a_2,b_1+b_2]\)(32-bit addition, with potential overflow)
Page: 54
Chapter: 4
Section: 2
Variables: \(a_i\stackrel{u}{\le}x_i\stackrel{u}{\le}b_i\) 32-bits integers
Kind: Theo
Prefix Greater: \(x_i+x_i\)'s belongs to
Assuming: all numbers unsigned

Smaller0: \(a_1-b_2\ge 0\) or \(b_1-a_2<0\) (mathematical substraction, without overflow)
Greater0: \(x_1-x_2\)'s belongs to \([a_1-b_2,b_1-a_2]\)(32-bit substraction, with potential overflow)
Page: 54
Chapter: 4
Section: 2
Variables: \(a_i\stackrel{u}{\le}x_i\stackrel{u}{\le}b_i\) 32-bits integers
Index: 5
Kind: Eq
Hide middle: yes
Assuming: all numbers unsigned

Smaller0: \(a\ne0\) or \(b=0\)
Greater0: \([-b,-a]\) (as unsigned int)
Page: 54
Chapter: 4
Section: 2
Variables: \(a\stackrel{u}{\le}x\stackrel{u}{\le}b\) 32-bits integers
Index: 6
Kind: Eq
Prefix Greater: \(-x\)'s belongs to
Assuming: all numbers unsigned

Page: 55
Implementation: \(a_1+a_2>=a_1 \&\& b_1+b_2<b_1\)
Section: 2
Chapter: 4
Effect: Whether addition \(x_1+x_2\) may potentially overflow
Variables: \(a_i\stackrel{u}{\le}x_i\stackrel{u}{\le}b_i\) bits integers
Index: 1
Kind: Fig
Assuming: all numbers unsigned

Page: 55
Implementation: \(a_1-b_2>=a_1 \&\& b_1-a_2<b_1\)
Section: 2
Chapter: 4
Effect: Whether \(x-y\) may potentially overflow
Variables: \(a_i\stackrel{u}{\le}x_i\stackrel{u}{\le}b_i\) unsigned bits integers
Index: 1
Kind: Fig

Smaller0: \(a_1+a_2\) and \(b_1+b_2<2^{32}\) both overflows negatively, both overflow positively or neither overflow
Greater0: \(x_1+x_2\)'s belongs to \([a_1+a_2,b_1+b_2]\)(signed 32-bit addition, with potential overflow)
Page: 56
Chapter: 4
Section: 2
Variables: \(a_i\stackrel{u}{\le}x_i\stackrel{u}{\le}b_i\) signed 32-bits integers
Index: 8
Kind: Eq

Smaller0: \(a\ne-2^{31}\)
Greater0: \(-x\)'s belongs to \([-b,-a]\) (as signed 32-bit int)
Page: 57
Chapter: 4
Section: 2
Variables: \(a\stackrel{u}{\le}x\stackrel{u}{\le}b\) 32-bits integers
Assuming: Signed integers

Smaller0: \(a_1-b_2\) and \(b_1-a_2<2^{32}\) both overflows negatively, both overflow positively or neither overflow
Greater0: \(x_1-x_2\)'s belongs to \([a_1-b_2,b_1-a_2]\)(32-bit substraction, with potential overflow)
Page: 56
Chapter: 4
Section: 2
Variables: \(a_i\stackrel{u}{\le}x_i\stackrel{u}{\le}b_i\) integers
Hide middle: yes
Assuming: signed integers

Page: 57
Variables: \(a_i\stackrel{u}{\le}x_i\stackrel{u}{\le}b_i\) signed bits integers
Expression: \(s=\sum a_i;\)
\(t=\sum b_i;\)
\(u=a_i\&a_2\&(\sim s)\&\sim(b_1\&b_2\&(\sim t));\)
\(v=((a_1\text{\textasciicircum}{} a_1)|\sim(a_1\text{\textasciicircum}s))\&((\sim b_1)\&(\sim b_2)\sim t)\)
\(u|v\)
Chapter: 4
Section: 2
Numeric: Whether \(x-y\) may potentially overflow, in sign bit
Explanation: \(u\):whether \(\sum a_i\) overflows in the negative direction, \(\sum b_i\) does not.
\(v\):whether \(\sum a_i\) does not overflow, \(\sum b_i\) overflows in positive direction.
In sign bit
Kind: Fig

Question: A lower bound for \((x_1|x_2)\) is
Answer: \(\text{max}(a_1,a_2)\)
Page: 58
Chapter: 4
Section: 3
Variables: \(a_i\stackrel{u}{\le}x_i\stackrel{u}{\le}b_i\) unsigned 32-bits integers

Question: A lower bound for \((x_1\&x_2)\) is
Answer: 0
Page: 58
Chapter: 4
Section: 3
Variables: \(a_i\stackrel{u}{\le}x_i\stackrel{u}{\le}b_i\) unsigned 32-bits integers
Assuming: Unsigned

Question: A lower bound for \((x_1\oplus x_2)\) is
Answer: 0
Page: 58
Chapter: 4
Section: 3
Variables: \(a_i\stackrel{u}{\le}x_i\stackrel{u}{\le}b_i\) unsigned 32-bits integers
Assuming: Unsigned

Question: An upper bound for \((x_1\oplus x_2)\) is
Answer: \(\min(b_1+b_2, 2^{32}-1)\)
Page: 58
Chapter: 4
Section: 3
Variables: \(a_i\stackrel{u}{\le}x_i\stackrel{u}{\le}b_i\) unsigned 32-bits integers
Assuming: Unsigned

Question: An upper bound for \((x_1\& x_2)\) is
Answer: \(\min(b_1,b_2)\)
Page: 58
Chapter: 4
Section: 3
Variables: \(a_i\stackrel{u}{\le}x_i\stackrel{u}{\le}b_i\) unsigned 32-bits integers
Assuming: Unsigned

Question: An upper bound for \((x_1| x_2)\) is
Answer: \(\min(b_1+b_2, 2^{32}-1)\)
Page: 58
Chapter: 4
Section: 3
Variables: \(a_i\stackrel{u}{\le}x_i\stackrel{u}{\le}b_i\) unsigned 32-bits integers
Assuming: Unsigned

Question: An upper bound for \(\neg x\) is
Answer: \(\neg a\)
Page: 58
Chapter: 4
Section: 3
Variables: \(a\stackrel{u}{\le}x\stackrel{u}{\le}b\) unsigned 32-bits integers
Assuming: Unsigned

Question: A lower bound for \(\neg x\) is
Answer: \(\neg b=2^{32}-1-b\)
Page: 58
Chapter: 4
Section: 3
Variables: \(a\stackrel{u}{\le}x\stackrel{u}{\le}b\) unsigned 32-bits integers
Assuming: Unsigned

Page: 58
Implementation: \(\neg a\)
Section: 3
Chapter: 4
Effect: \(2^{32}-1-a\)
Variables: \(a\) an unsigned 32 bit integer
Extra: Not in the book

Page: 59
Variables: \(a_i\stackrel{u}{\le}x_i\stackrel{u}{\le}b_i\) signed bits integers
Expression: m=0x8000000>>nlz(a^c)
while (m!=0){
  if (~a&c&m){
    tmp=(a|m)&-m;
    if(tmp<=b){a=tmp;break;}
   }else{
     tmp=(c|m)&-m;
     if (tmp<=d){c=tmp;break;}
  }
  m=m>>1;
return a|c;
Chapter: 4
Section: 3
Numeric: The minimal of \(x_1|x_2\) according to above mentioned constraint
Explanation: Let \(n\) be the least integer such that the \(n\)-th bit of \(a_i\) is 0 and \(a_{3-i}\) is 1, sucht hat switching it to 1 in \(a_{i}\), and every following bits to 0, lead to a number less than \(b_i\).
Let \(a_i'\) be this number, then the result is \(a'_i|a_{3-i}\)
Kind: Fig