6
$\begingroup$

How many $1$s are in the first $1023$ binary numbers?

I'm not to sure how to approach this question. An idea, formula, or solution is appreciated!

$\endgroup$
6
  • 4
    $\begingroup$ Have you noticed that $1023 = 2^{10}-1$? $\endgroup$ Feb 26 '17 at 0:20
  • 6
    $\begingroup$ What is the "first" binary number? 0 or 1? $\endgroup$
    – Anonymous
    Feb 26 '17 at 0:22
  • $\begingroup$ Worth clarifying that we are talking about positive, unsigned integers. $\endgroup$
    – J...
    Feb 26 '17 at 2:09
  • $\begingroup$ @J... actually, can an unsigned integer be positive? $\endgroup$
    – Joffan
    Feb 26 '17 at 5:56
  • $\begingroup$ @Joffan Cheeky bastard :P Yes, unsigned integers are positive because all of them (other than 0) are greater than 0. $\endgroup$
    – Navin
    Feb 26 '17 at 9:35
21
$\begingroup$

Assuming the "first" binary number is $1$ note that the first $1023$ binary numbers, plus $0$, are all the binary numbers you can write with exactly $10$ binary digits or bits (prepending $0$s to "short" numbers, as in $0000101010_2$). Between all of them, you then have $1024 \cdot 10=10240$ bits, and for symmetry reasons exactly half of those, $5120$, are $1$s.

$\endgroup$
15
  • $\begingroup$ why 1024*10 digits? $\endgroup$
    – user406996
    Feb 26 '17 at 0:28
  • 2
    $\begingroup$ Ohh, the amount of 0's don't matter! I see! $\endgroup$
    – user406996
    Feb 26 '17 at 0:29
  • 3
    $\begingroup$ It does matter, because if we start at 0, then 1111111111 should not be counted among the the first 1023 binary numbers. The question did not say the first 1023 positive binary numbers. $\endgroup$
    – Dominic108
    Feb 26 '17 at 2:23
  • 1
    $\begingroup$ In computer science, typically indexing start at 0. I was biased . I should have read the comments below the question... The issue was raised before. $\endgroup$
    – Dominic108
    Feb 26 '17 at 2:52
  • 1
    $\begingroup$ @MarDev We're looking at all of the integers we can represent with 10 bits - for every integer there is exactly one other which has all of its bits inverted (the result of an XOR with 1111111111) and therefore the opposite amount of zeros and ones. Furthermore, this inversion always lies in the opposite half of the possible numbers (the operation is essentially equivalent to 1111111111 - n) so each of the first 2^9 numbers (half of the possible 2^10) there exists exactly one number in the second half with the opposite number of zeros and ones. $\endgroup$
    – acernine
    Feb 26 '17 at 8:46
9
$\begingroup$

Hint: For how many of those numbers will the one's bit be a $1$ (in other words: how many of those numbers are odd)? For how many of them will the two's bit be a $1$? For how many of them will the four's bit be a $1$? And so on. Also, it will probably be advantageous to include $0$ (and thus look at a collection of $1024$ binary numbers) to make the counting a bit easier. Or, if $0$ is already included, include $1023$ initially, then correct for it when you're done counting.

$\endgroup$
2
  • $\begingroup$ I'm struggling with that idea right now. I'm not entirely sure how to solve that. Is it like half half? So if there are x digits in total, half of them are 1? $\endgroup$
    – user406996
    Feb 26 '17 at 0:27
  • $\begingroup$ On average, yes, half of the bits will be a $1$. Or something. Depends on what you mean by "of the bits". $\endgroup$
    – Arthur
    Feb 26 '17 at 0:31
8
$\begingroup$

Any such number can be represented by a string of 10 0s and 1s. The number of such strings with $n$ ones is $10$ choose $n$. Thus, the number of ones which appear is $$ \sum_{n=0}^{10} n{10 \choose n}=5\cdot 2^{10}. $$

$\endgroup$
4
$\begingroup$

As an addendum to Arthur's answer - if you count to, say, $2^{4} - 1 = 15$, you can easily figure out a pattern in the columns:

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

So if you count to $2^{n} - 1$, you have $2^{n} * n$ digits ("rows * columns"), of which 50% are 1's.

For your example: Counting to $1023 =2^{10} - 1$, gets you $2^{10} * 10 * \frac{1}{2} = 5120$ binary 1's in total.

$\endgroup$
1
$\begingroup$

It's easy to calculate. There is a pattern with any number used as pow of tow:

You have 2^x, where x> 0 and you will have a binary number as:

2^0 = 1 (Dec) = 1 (Binary)

2^1 = 2 (Dec) = 10 (Binary)

2^2 = 4 (Dec) = 100 (Binary)

...

2^10 = 1024 (Dec) = 100 0000 0000(Binary)

If you pay attention you will notice this:

2^10 - 1 = 1023 (Dec) = 011 1111 1111(Binary)

...

2^2 - 1 = 3 (Dec) = 011 (Binary)

2^1 = 1(Dec) = 01 (Binary)

2^0 - 1 = 0 (Dec) = 0 (Binary)

In this case, your question, the Number of ones matches with the number that is used for pow.

$\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.