2
$\begingroup$

Most programming languages have functions for getting bits but I need to do it on a calculator so I need to understand how to do it mathematically. Basically I need a formula for getting the $n$th bit from and integer, $i$.

So given: $i = 6$ and $n = 3$, I would get $1$ because binary for $6$ is $110$.

How might I manage this?

$\endgroup$
1
  • 1
    $\begingroup$ Exactly what functions are at your disposal? Just +, -, *, and /? Do you have a floor function on your calculator? Sine? The answer to this question all depends on what functions are available (it can't be done with just +, -, *, and /). $\endgroup$ Commented Feb 10, 2014 at 5:59

4 Answers 4

3
$\begingroup$

Given $i$ you want to throw away the bottom $n-1$ bits, so integer divide by $2^{n-1}$. Then take $\bmod 2$ to get the low order bit.

$\endgroup$
2
$\begingroup$

Another very useful formula for the $k$-th bit of number $b=b_{n}\cdots b_{0}$ is $$b_{k}=\left\lfloor\frac{b}{2^k}\right\rfloor-2\left\lfloor\frac{b}{2^{k+1}}\right\rfloor.$$ This identity can be easily verified by using that, for $b=\sum_{i=0}^{n}b_{i}2^{i}$, we have $\left\lfloor\frac{b}{2^k}\right\rfloor=\sum_{i=k}^{n}b_{i}2^{i-k}$.

$\endgroup$
2
  • $\begingroup$ Can someone explain what the $-2 \lfloor \frac{b}{2^{k+1}} \rfloor$ does $\endgroup$ Commented Apr 2, 2022 at 19:58
  • $\begingroup$ @NeelSandell, note that $\left\lfloor\frac{b}{2^k}\right\rfloor$ is equivalent to b>>k, and $\left\lfloor\frac{b}{2^{k+1}}\right\rfloor$ to b>>k+1, which truncates the last bit after the division by $k$, $2*\left\lfloor\frac{b}{2^{k+1}}\right\rfloor$ is equivalent to b>>k+1<<1, which is b>>k&~1, and (b>>k)-(b>>k&~1)=b>>k&1, the $k$th bit. $\endgroup$ Commented Jul 14, 2023 at 14:48
0
$\begingroup$

Most calculators have a way to truncate fractions. So to get bit #3 here are the steps

  1. Divide $i$ by $2^{n}$ and truncate the fractional part
  2. Divide the quotient by $2$ and take the remainder, i.e. check if it is odd or even

Example: Find the bit #5 of $111$.

$$2^5=32$$ So $$ 111/32=3.46875 $$ The truncated value is $3$. Now, $3$ divided by $2$ leaves $1$ as remainder (odd number). So bit #5 is $1$.

Repeat for bit #4. $$ 2^4=16$$. So $$ 111/16 = 6.9375 $$ Truncated answer is $6$ which is even. So bit #4 is zero.

$\endgroup$
0
$\begingroup$

If you can use mod then its easy: ((value - (value mod (2^n))) / (2^n)) mod 2

Otherwise bit0 is (1+(-1^(value+1)))/2 - applicable for any integer value or any function that returns integer value. Attempts to emulate mod of a function may lead to result which also contain mod operation.

To get n-th bit,

first lets shift value/function: shift right is (valuable - bit 0) / 2 - apply n times.

next get bit0 as described.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .