3
$\begingroup$

How one can deduce that if b is any number and if b%2==1 then rightmost digit of b in binary form will be 1 without checking it manualy

$\endgroup$
  • 15
    $\begingroup$ Here's a related question. How do you know that if $d$ is any number and if $d \% 10 \equiv 1$, then the rightmost digit of $d$ in base-10 is 1. $\endgroup$ – davidlowryduda Oct 5 '15 at 1:26
  • 1
    $\begingroup$ Because it's a tautology, or identity if you prefer. $\endgroup$ – user207421 Oct 5 '15 at 3:07
  • 2
    $\begingroup$ Doesn't seem to be true for $b = \pi$. $\endgroup$ – Eric Towers Oct 5 '15 at 4:29
  • 15
    $\begingroup$ @EricTowers There is no rightmost digit of $\pi$ and $\pi\%2\ne 1$, so ... $\endgroup$ – Hagen von Eitzen Oct 5 '15 at 8:19
  • $\begingroup$ @HagenvonEitzen : Have you used a language where "%" was not an integer operator? I haven't. In those languages, $\pi$ is coerced to "3" before the reduction. Then, as you say, ... $\endgroup$ – Eric Towers Oct 6 '15 at 16:12
17
$\begingroup$

b % 2 means "the remainder when you divide by 2".

A binary number like $101001$ can be written:

$$1 * 2^5 + 0 * 2^4 + 1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 1*2^0$$

which is

$$1 * 32 + 0 * 16 + 1 * 8 + 0 * 4 + 0 * 2 + 1*1$$

If you get rid of everything that is divisible by $2$ (since it will all go away when you divide by $2$ and take the remainder) you get:

$$1*1 = 1$$

If the last digit of our number was $0$, we would have gotten zero instead.

This is the same as saying a number is even if and only if its least significant bit is 0 (binary) -- otherwise it's odd.

$\endgroup$
9
$\begingroup$

Expressing $b$ in binary we get $$b=b_n2^n+b_{n-1}2^{n-1}+\cdots+b_22^2+b_12^1+b_02^0$$ where each of $b_n, b_{n-1},\ldots, b_1$ are either $0$ or $1$. Now, when we take this modulo $2$, every summand disappears except for $b_02^0=b_0$, which is the rightmost binary digit of $b$.

$\endgroup$
6
$\begingroup$

HINT :

Let $$b=b_0+2b_1+2^2b_2+...+2^nb_n$$

What do you get when you calculate $b\bmod 2$?

$\endgroup$
1
$\begingroup$

You only need to demonstrate that it is 1 when there is only 1 digit to prove that it will be 1 for any odd number, regardless of the number of digits.

It's a base two number: the last digit can only be 1 or 0. When you add 1 to 0 it will go to 1 and when you add another it goes back to 0 and the number of digits increases by 1. Since it can only be one or the other, and zero is even, then all odd numbers will have a 1 as the right most digit.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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