1
$\begingroup$

How do I access the bit at a particular index in a number using shift operator. Say the number is $n$.
Let the index be $i (i: 0 \le i < n).$
Rightmost bit is $0$.

The only thing I can think of is:
$def \, bitAt(n, i)$
$\,\,\,\,\,\,\,\,m = n >> i+1$
$\,\,\,\,\,\,\,\,v = n >> i$
$\,\,\,\,\,\,\,\,m = m << 1$
$\,\,\,\,\,\,\,\,if(m == v)$
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,return \, 0$
$\,\,\,\,\,\,\,\,else$
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,return \, 1$
$\,\,\,\,\,\,\,\,end$
$end$

Is there a more efficient way to do this?

Improve this question
$\endgroup$
4
  • $\begingroup$ I'm not exactly sure about efficiency, but this also works: if ((n << i) & n) == 0 return 0 else return 1. What this does is create a number with the ith bit set to one, then AND this with the original number, if that bit is 1 in the original number, the result is n << 1, otherwise it becomes zero. $\endgroup$ – Mahdi Sep 30 '17 at 12:41
  • $\begingroup$ Are you sure about it? (n << i) should just set the first i bits to 0. The ith bit is set to the LSB. It's not clear to me how using and on the two will determine the bit that was the LSB? Or the ith bit if that was the aim. $\endgroup$ – Tobi Alafin Sep 30 '17 at 12:49
  • $\begingroup$ Ah sorry, there is a typo there, I meant ((1 << i) & n) == 0 in the conditional, 1 << i sets the ith bit to 1. $\endgroup$ – Mahdi Sep 30 '17 at 12:54
  • $\begingroup$ Thanks, this would work. Make it an answer (even if it's not more efficient (which I doubt (I think it's more efficient)) It is shorter than my algorithm, which is a bonus. $\endgroup$ – Tobi Alafin Sep 30 '17 at 12:57
2
$\begingroup$

This can be done by running an AND between n and a number with it's ith bit set to 1, which can be obtained by 1 << i. The result of this operation will be zero if the ith bit in n is zero, or 1 << i otherwise.

Case of zero:

n     = 10111
m     = 01000 (1 << 3)
n & m = 00000

Case of one:

n     = 10111
m     = 00100 (1 << 2)
n & m = 00100 (1 << 2)

So:

$m = 1 << i$

$\text{if}\; (n \;\&\; m == 0)$

$\;\;\;\;\text{return} \;0$

$\text{else}$

$\;\;\;\;\text{return} \;1$

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.