Questions tagged [binary]

Questions related with (base 2) representation of numbers and their unique properties arising out of number representation.

Filter by
Sorted by
Tagged with
68
votes
18answers
11k views

What are the names of numbers in the binary system?

The names we use are very much related to the radix we use $0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9$ zero - one - two - three - four - five - six - seven - eight -nine We repeat the names $21$ twenty ...
40
votes
12answers
6k views

In plain English, why does conversion from hexadecimal to binary work so cleanly?

Why does the trick of taking the binary representation of each digit and simply concatenating them work? e.g. 0x4E == 0100 ...
34
votes
3answers
3k views

What is the probability that eventually it will rain forever?

Probability of raining today is 60%. If it rains today, the probability of raining tomorrow will increase by 10%. If it doesn't rain today, the probability raining tomorrow will decrease by 10%. Rule ...
29
votes
7answers
10k views

Is there a way to find the log of very large numbers?

I should like to evaluate $\log_2{256!}$ or other large numbers to find 'bits' of information. For example, I'd need three bits of information to represent the seven days of the week since $\lceil \...
23
votes
8answers
15k views

Fractions in binary?

How would you write a fraction in binary numbers; for example, $1/4$, which is $.25$? I know how to write binary of whole numbers such as 6, being $110$, but how would one write fractions?
23
votes
3answers
3k views

What do bitwise operators look like in 3d?

The hypothetical relation is $z = \mathrm{xor}\left(x,y\right)$ where xor is any bitwise operator such as AND, OR, NAND, etc. I see that these operations may be defined for integers trivially using ...
18
votes
4answers
4k views

Why are binary representations of huge numbers about $3.3218$ times as long as their decimal representations?

Why are huge binary nubers about $3.3218$ times longer than their decimal counterpart? I thought about this when I was writing this Python code: ...
17
votes
4answers
797 views

$N$ perfect logicians wearing hats

I once came across the following riddle: (assume $N$ to be extremely large) There are $N$ perfect logicians arranged in a vertical row. They are allowed to strategize before the game, during the ...
16
votes
3answers
67k views

How can I convert 2's complement to decimal?

Suppose I have the 2's complement, negative number 1111 1111 1011 0101 (0xFFBB5). How can I represent this as a decimal number in base 10?
16
votes
4answers
5k views

Why Two's Complement works

About to read computer science, I have just stumbled accross the concept of "Two's complement". I understand how to apply the "algorithm" to calculate these on paper, but I have not yet obtained an ...
16
votes
1answer
7k views

What is meaning of strict weak ordering in layman's term? [closed]

I gone through many pages using Google, but not understand exact meaning of Strict-weak Ordering term. I have this requirement while sorting strings.
14
votes
1answer
574 views

Find $\sum_{n=1}^\infty {\frac {f(n)} {n(n+1)}}$ where $f(n)$ is the number of $1$s in $n$'s binary expansion

We are given the series $\sum_{n=1}^\infty {\frac {f(n)} {n(n+1)}}$, where $f(n)$ is such a function that it equals the sum of 1's in the binary representation of n. I'm obliged to find the sum of ...
13
votes
2answers
978 views

The sum of powers of two and two's complement – is there a deeper meaning behind this?

Probably everyone has once come across the following "theorem" with corresponding "proof": $$\sum_{n=0}^\infty 2^n = -1$$ Proof: $\sum_{n=0}^\infty q^n = 1/(1-q)$. Insert $q=2$ to get the result. Of ...
13
votes
1answer
279 views

The proportion of binary digits of $\sum_{k=1}^\infty \Big\lfloor{\frac{k}{2}\sqrt{p}\Big\rfloor}\cdot2^{-k}$ equal to one, is $> 0.978$ if $p=143$.

Can you prove this? Is it true? If $p$ is an integer, is this proportion never equal to 50%? See my related question regarding this sum, here. For $p=143$, I computed the binary digits in Excel using ...
12
votes
4answers
2k views

Is Cantor's diagonal argument dependent on the base used?

Applying Cantor's diagonal argument to irrational numbers represented in binary, one and only one irrational number can be generated that is not on the list. Wikipedia image: But if you change the ...
11
votes
2answers
2k views

Why are binary numbers ordered the way they are? [duplicate]

Counting to 7 in binary looks like this: 0 1 10 11 100 101 110 111 The highest value is always to the left. But would it make more sense to to it like this? Is there a way that this was picked, or ...
11
votes
3answers
6k views

Why do we divide or multiply by 2 when converting binary?

Trying to understand the fundamentals of binary rather than just following steps, I wanted to know why do we multiply by 2 to convert a decimal (0.5, 0.25) to a binary and why do we divide by 2 when ...
11
votes
2answers
423 views

Sum of series with binary parity in the numerator

I'm now stuck with this question, and I don't even know where to start: Find sum of series$$\sum_1^\infty \frac{f(n)}{n(n+1)}$$, where f(n) - number of ones in binary representation of n. I wish I ...
11
votes
3answers
3k views

It it possible to “compress” a list of large numbers using their prime factors?

On a computer I can have integers on arbitrary size thanks to GMP, so it's represented in base 2 in memory. I'm wondering if it's possible in theory to use less memory if I store only prime factors ...
11
votes
3answers
276 views

Why do so many computer programming language implementations have trouble with the remainders of negative integers?

As most of us know, or should know, $-7 \equiv 1 \pmod 4$. But if you use Java's modulus operator %, you get -3 for the answer, ...
11
votes
1answer
791 views

Finding Expressively Adequate truth Functions

I was wondering if someone could help me count the total number of Truth Functions of 3 variables, that can generate all the possible truth functions.. I got 56 but I'm not sure of the answer. EDIT: ...
10
votes
2answers
1k views

Why does the $2$'s and $1$'s complement subtraction works?

The algorithm for $2$'s complement and $1$'s complement subtraction is tad simple: $1.$ Find the $1$'s or $2$'s complement of the subtrahend. $2.$ Add it with minuend. $3.$ If there is no carry then ...
10
votes
2answers
44k views

Modulo 2 binary division (XOR not subtracting) method

I have attached an image showing a Modulo 2 binary division. I can roughly understand the working below which is using XOR calculation but I am not sure how the answer (in red) is being computed ...
10
votes
0answers
362 views

Number of ways to express a binary number in a certain way

So I'm working on a problem where I get to a point where I have to count the number of solutions to an equation or at least find a decent upper bound to be used in an estimate I need later. The ...
9
votes
8answers
2k views

Some doubts in 2's complement

I am doing one question in which we have to find 2's complement of 43. I know to find 2's complement we have to find 1's complement and then add 1 into it to get 2's complement. So here is how I am ...
9
votes
1answer
279 views

Second digit of square numbers in binary yields $\sqrt2$

Why do ratios of terms in sequences based on $2$nd binary digit of $2$nd power, converge to $\sqrt2$? Update: Added at the bottom of the post a generalization for all other bases,powers, and digits. ...
9
votes
3answers
3k views

Why does the division algorithm work for converting between number bases?

I know and have observed that the the division algorithm can be used to convert any number in the decimal system to the binary system. However, I have tried searching for an intuition of why this ...
9
votes
4answers
18k views

How can I generate the binary representation of any real number?

In p. 30 of Baby Rudin, I find a reference to the fact that the binary representation of a real number implies the uncountablity of the set of real numbers. But I have two questions: Does every real ...
9
votes
1answer
754 views

Why does the following formula increment a negabinary number (number in base -2)?

In a file I have written the following formula that increments a negabinary number (a number in base -2): $$2x \oplus ((2x \oplus x) + 1) $$ In this formula $x$ is a negabinary number interpreted as ...
8
votes
2answers
8k views

Count the number of n-bit strings with an even number of zeros.

I am currently self-studying introductory combinatorics by reading Introduction to combinatorial mathematics. I am currently in the first chapter, and I have a question regarding one of the examples. ...
8
votes
2answers
158 views

What is the least prime which has 32 1-bits?

On the many prime number investigation sites across the web I haven't been able to find the answer. Also my math isn't good enough to compute it from first principles. So, what is the least prime ...
8
votes
2answers
115 views

Are the high-order bits of $n^2$ as likely to be zeroes as ones?

Let $B_i(n)$ be the $i$th bit in the binary expansion of $n$, so that $n=\sum B_i(n)2^i$. Now let $n$ be randomly and uniformly chosen from some large range, and let $E(j)$ be the expected value of $...
8
votes
1answer
181 views

Do primes, expressed in binary, have more “random” bits on average than natural numbers?

In my programming projects I sometimes pick large primes when I want somewhat "random" bits, e.g. for hashing or trivial obfuscation via XOR or modular mutiplication. My intuitive sense is that primes ...
8
votes
1answer
4k views

Finding the binary representation of the $n$th Fibonacci term

Objective: To find the binary representation ( or no. of 1's in binary representation) of nth term in Fibonacci sequence where n is of the order 10^6. My current approach: Find nth term (in decimal) ...
8
votes
0answers
359 views

New numeration system, mapping to binary numeration system

Let us consider $$Z = X_1 + X_1 X_2 + X_1 X_2 X_3 + \cdots.$$ Here the $X_i$'s can only take on two different values: either $X_i=a$ or $X_i=b$, with $0 < a < b < 1$ and $a+b = 1$. The $n$-...
8
votes
0answers
127 views

Fraction of $1$s in binary representation of $n!$

I plotted a fraction of $1$s in binary representation of $n!$ (i.e. A079584/A072831) for $n$ from $1$ to $10^4$: It appears it might converge to some limit for $n\to\infty$. Can we (dis-)prove that ...
7
votes
2answers
309 views

Why do division algebras always have a number of dimensions which is a power of $2$?

Why do number systems always have a number of dimensions which is a power of $2$? Real numbers: $2^0 = 1$ dimension. Complex numbers: $2^1 = 2$ dimensions. Quaternions: $2^2 = 4$ dimensions. ...
7
votes
3answers
2k views

Number of binary strings with $n$ ones and $m$ zeros

$f(n,m)$ is the number of binary strings with up to $n$ ones and up to $m$ zeros. Prove that the number of possible strings is: $${n+m+2 \choose n+1} -1$$ I got to the point that: $$\sum_{a=0}^n \...
7
votes
1answer
20k views

How many bits needed to store a number

How many bits needed to store a number $55^{2002}$ ? My answer is $2002\;\log_2(55)$; is it correct?
7
votes
2answers
2k views

Nim addition- binary addition without carrying

A nim addition table is essentially created by putting, in any cell, the smallest number not to the left of the cell and not above that cell in its column. However, I know for a fact that nim addition ...
7
votes
1answer
141 views

Is the link between Stern's diatomic sequence and binary subsequences genuine or a coincidence with exceptions?

In a sister stack, Martin Ender raised a question about the following function: Let's define a function $f(N)$ on the integers via the following algorithm. We'll use $N = 38$ as an example: ...
7
votes
2answers
2k views

Random binary matrix with given rows and columns sums

I need to generate a random binary matrix $(n, n)$ whose rows sums and columns sums are $4$. I don't manage to find a quite efficient algorithm to do this. Have you an idea please ? NB : The ...
7
votes
1answer
147 views

Binary weight of OEIS sequence A308092.

Preliminaries OEIS sequence A308092 is defined as: The sum of the first $n$ terms of the sequence is the concatenation of the first $n$ bits of the sequence read as binary, with $a(1) = 1$. And ...
7
votes
1answer
302 views

Matrix + combinatorial or conditional probability: bit patterns

I'm trying to get my head around a problem, and it's not working. The problem: consider an NxN matrix that represents a binary number. For instance, a 4x4 matrix is a 16 bit number, a 6x6 matrix is ...
6
votes
5answers
1k views

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

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!
6
votes
6answers
1k views

Is there an easy way to see that binary expansion is unique? [duplicate]

Let $n \in \mathbb{N}$. Using the Euclidean algorithm, it is straightforward to see that every natural number can be written as $$n = \sum_{j=0}^m \epsilon_j(n) 2^j $$ where $\epsilon_j(n) \in \{0,1\...
6
votes
8answers
10k views

$f(x) = 0$ when $x$ is $0$, and $1$ otherwise

I've been trying to create a function that will return $0$ when $x$ is $0$, and for any other $x$ value it should return $1$. I've searched for a pre-existing function online too and wasn't able to ...
6
votes
3answers
1k views

What is the next number having the same number of bit 1s? [duplicate]

You are given a number, $A$, and you have to determine a number, $B$, such that $B>A$ and the number of $1's$ in the binary representation of $A =$ number of $1's$ in the binary representation of $...
6
votes
4answers
888 views

Number of binary sequences with no consecutive ones.

So I've got a problem that says "How many ways are there go give $k$-identical biscuits to $n$-different children if each child gets at least one biscuit?" I figured I'd do it using binary sequence. ...
6
votes
2answers
4k views

Algorithm for creating binary rational numbers

I read here an algorithm to convert a decimal rational number to binary by multiplications by 2, but although it's very simple to carry on, I still haven't managed to explain myself why it works. ...

1
2 3 4 5
28