2
$\begingroup$

What is the number of 1s in the binary representation of

$$3\times512 + 7\times64 + 5\times8 + 3$$

Is there any shortcut for finding the number of $1's$ and $0's$ in a binary number which has been factored as above?

$\endgroup$
0

4 Answers 4

5
$\begingroup$

Yes.

Powers of 2 will just offset their constant multipliers in the binary representation, equivalent to bitshift left or right. The constants here are "narrower" than their accompanying shifts, so you don't have to worry about "carrying" any 1s in the sum.

(Aside: This becomes quickly clear once you recognize that the number has been factored into octal, where it would be written 03753. While hexadecimal digits correspond to 4 bits each in binary, octal digits correspond to 3 bits each, so it's very easy to expand to its binary representation once you recognize this.)

So you can look solely at the multipliers: 3, 7, 5, 3. Count the 1s present in each of these in binary, and then the 0s, and you have your answer. No multiplication required!

$\endgroup$
2
  • $\begingroup$ That means 8 is 1000, will the 1 in this 8 be counted? $\endgroup$ Dec 10, 2013 at 14:10
  • $\begingroup$ No, we are looking at the constant factors. The *512, *64, *8, *1 parts are just shifting their constant factors to the left in the binary representation: 3*8_10 = 11_2 * 1000_2 = 11000_2 aka 11 shifted 3 spaces to the left. $\endgroup$
    – Jeremy W. Sherman
    Dec 10, 2013 at 14:14
2
$\begingroup$

You need to imagine the binary representation in your head. Maybe you are a programmer, so you should know the powers of 2, and thus it shouldn't be really hard to imagine, how the binary representation of this number will see:

3*512 = 11 * 1000000000
7*64 = 111 *    1000000
5*8 = 101 *        1000
3 =                  11

The sum of them will be 11111101011 . It is clearly visible if you had some experience in such arithmetics, if not, you can do this nearly so easy on a paper.

Thus, the answer is: 9.

$\endgroup$
0
1
$\begingroup$

I would say in general, no (there is no shortcut), but in your problem because the factors are powers of 2 and because they are "spread out" enough and don't overlap, you can just count the number of 1's in each factor: 3, 7, 5, and 3, and you get 2 + 3 + 2 + 2 = 9. But if the terms hadn't been even factors of 2, or if they hadn't been separated far enough, this wouldn't work, because they would have impacted each other with the addition, e.g. 3*8 + 3*16 doesn't result in a 2 + 2 count of 1's. It results in 9*8 which has two 1's.

The number of zeros is a bit trickier--you have to figure out the first power of 2 which is larger than your number and subtract the number of 1's from that value.

$\endgroup$
1
$\begingroup$
  1. 110 0000 0000 - 1536
  2. 001 1100 0000 - 448
  3. 000 0010 1000 - 40
  4. 000 0000 0011 - 3

Answer: 111 1110 1011 - 2,274

The method I have used is base 2 arithmetic.

In the end the number of 1's can be calculated by converting each number into a binary number, adding the numbers together using the method above, and counting the number of 1's and 0's in the calculated result.

$\endgroup$
2
  • $\begingroup$ You misinterpreted the question. He want to know the number of the 1-s in the binary representation, he didn't ask to calculate this for him. $\endgroup$
    – peterh
    Dec 10, 2013 at 13:53
  • 3
    $\begingroup$ @PeterHorvath - I didn't misinterpret anything. $\endgroup$
    – Ramhound
    Dec 10, 2013 at 14:07

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.