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

learn more… | top users | synonyms

32
votes
10answers
4k 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 ...
19
votes
3answers
1k 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 ...
16
votes
3answers
3k views

Why are huge binary numbers about 3.3218 times longer than their decimal counterpart?

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: ...
15
votes
8answers
4k 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?
12
votes
4answers
1k 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 ...
10
votes
2answers
346 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 ...
10
votes
1answer
510 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 ...
10
votes
1answer
491 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: ...
8
votes
2answers
2k 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 ...
8
votes
2answers
84 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
3answers
4k views

Convert the following hexadecimal representation of 2’s complement binary numbers to decimal numbers.

I need to convert the following hexadecimal representation of 2’s complement binary numbers to decimal numbers I am unsure if I am doing it correctly or am I missing a step? a. xF0 b. x7FF c. ...
7
votes
2answers
305 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 ...
7
votes
1answer
130 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 ...
7
votes
0answers
179 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 ...
6
votes
1answer
156 views

Why is $2^{16}=65536$ the only power of $2$ less than $2^{31000}$ that doesn't contain the digits $1$, $2$, $4$ or $8$ in its decimal representation?

$65536$ is the only power of $2$ less than $2^{31000}$ that does not contain the digits $1$, $2$, $4$ or $8$ in its decimal representation. http://en.wikipedia.org/wiki/65536_%28number%29
6
votes
2answers
445 views

Complement of all-one vector in binary vector space

Let $V$ be a k-dimensional subspace of $(\mathbb{F}_2)^n$, such that vector $\vec{j}=(1,1,...,1) \in V$. Standard linear algebra shows that it is possible to find a $(k-1)$-dimensional space $W$ such ...
6
votes
1answer
746 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) ...
5
votes
10answers
598 views

Function that sends $1,2,3,4$ to $0,1,1,0$ respectively

I already got tired trying to think of a function $f:\{1,2,3,4\}\rightarrow \{0,1,1,0\}$ in other words: $$f(1)=0\\f(2)=1\\f(3)=1\\f(4)=0$$ Don't suggest division in integers; it will not pass for ...
5
votes
5answers
83 views

How many bit strings of length $12$ have a substring $01$?

My question is should it be $11C2$ or should it be $11C1$? Since $01$ are connected together, I take them as a single unit and there are $11$ different positions where they can be placed. Is the ...
5
votes
2answers
15k 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?
5
votes
2answers
411 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 ...
5
votes
4answers
183 views

Floor function to the base 2

I'm not a math guy, so I'm kinda confused about this. I have a program that needs to calculate the floor base $2$ number of a float. Let say a number $4$, that base $2$ floor would be $4$. Other ...
5
votes
1answer
472 views

Generating Function for Binary String Question

The following is an assignment question I have been trying to work out for quite some time. Let $C(x,y)=\sum_{n,k \geq 0} c_{n,k} x^{n} y^{k}$, where $c_{n,k}$ is the number of binary strings of ...
5
votes
1answer
185 views

Efficient division using binary math

I'm writing code for an FPGA and I need to divide a number by $1.024$. I could use floating and/or fixed point and instantiate a multiplier but I would like to see if I could do this multiplication ...
5
votes
2answers
401 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 ...
5
votes
2answers
85 views

Is there a name for the set of bit combinations of bitstrings?

Let $A \subset \{0,1\}^n$ be a set of $n$-bit bit vectors. Let me call a bit vector $b = (b^{(1)}, b^{(2)}, \dotsc, b^{(n)}) \in \{0,1\}^n$ a "bit combination" of the vectors in $A$ if: $$\forall i ...
5
votes
2answers
583 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 ...
5
votes
1answer
163 views

What function $f$ such that $a_1 \oplus\, \cdots\,\oplus a_n = 0$ implies $f(a_1) \oplus\, \cdots\,\oplus f(a_n) \neq 0$

For a certain algorithm, I need a function $f$ on integers such that $a_1 \oplus a_2 \oplus \, \cdots\,\oplus a_n = 0 \implies f(a_1) \oplus f(a_2) \oplus \, \cdots\,\oplus f(a_n) \neq 0$ (where the ...
5
votes
1answer
51 views

How many numbers from $1$ to $2^n$ will have $``11"$ as substring in binary representation?

For example say, $n = 2$. So our set is $\{1, 2, 3, 4\}$ in base $10$ and $\{1, 10, 11, 100\}$ in base $2$. So Output $1$, because only one number i.e. $3$ is there such that it has $``11"$ in it. ...
4
votes
3answers
288 views

An odd question about induction.

Given $n$ $0$'s and $n$ $1$'s distributed in any manner whatsoever around a circle, show, using induction on $n$, that it is possible to start at some number and proceed clockwise around the circle to ...
4
votes
2answers
2k 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. ...
4
votes
3answers
390 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 ...
4
votes
1answer
3k 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?
4
votes
1answer
62 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 ...
4
votes
1answer
354 views

Finding a rational number which is simply normal to relatively prime bases

Let $n\ge 2\in\mathbb Z$. Suppose that a base-$n$-decimal $(0.a_1a_2a_3\cdots)_n$ represents $\sum_{k=1}^{\infty}\frac{a_k}{n^k}$ where $a_{i}\in\{0,1,\cdots,n-1\}\ (i=1,2,\cdots)$ is each digit ...
4
votes
1answer
947 views

How can I solve simple equations involving binary operators?

I have some simple equations like: A = (X AND 1779038349) XOR ((X AND 3144134329) XOR 7047511487) Where A is some constant and X is unknown (all numbers are 32 ...
4
votes
4answers
5k views

binary representation of a real number

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

Fun ideas for project on Encoding

My university is organizing a project for college students (age around 17) around the subject of encoding (not encypting! See also http://danielmiessler.com/study/encoding_vs_encryption/). As a ...
4
votes
1answer
105 views

Disjoint subsets and Number of 1's in the binary representation

For a subset $S$ of $[n]$, let $\chi(S)$ denote the $n$ bit 'characterisitc vector' of $S$, i.e., $\chi(S)=(a_1, a_2, \ldots, a_n)$ where $a_i=1$ if $i \in S$ and $a_i=0 $ if $i \notin S$. Think of ...
4
votes
1answer
49 views

Least squares with matrix in $GF(2)$?

Here's an example of a problem I'm working on involving finding combination of bit vectors that yield a certain sum (in the $GF(2)$ sense): $ \begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 ...
4
votes
1answer
70 views

How many bits in position i are turned on in a list of values 0-N?

Is there an equation that reflects how many values have a bit in position $i$ turned on for a list of values $0-N$?. For example if $N=5$, our numbers are represented in binary as: 000, 001, 010, ...
4
votes
1answer
82 views

Proving that $A_2(13,7) = 8$

It is not too difficult to find a binary code consisting of $8$ words, each $13$ bits long, keeping the distance between every pair of words at least $7$. I know it is not possible to find $9$ words ...
4
votes
0answers
56 views

What is the explicit formula (solution) to this recursively defined binary matrix?

My question concerns the following binary matrix (call it matrix $A$). Or rather the entire family of such matrices, for some number of columns $n$ and rows $2^n$. The ellipses indicate that the ...
4
votes
1answer
115 views

XOR of Three Integers

How would you prove the following: Given three non-negative integers $a, b, c$; if $a \oplus b \oplus c = 0$ then $(a - k) \oplus (b - k) \oplus (c - k) > 0$ for any $0 < k \leq min(a, b, c)$ ? ...
4
votes
0answers
735 views

Binary representation of powers of 3

We write a power of 3 in bits in binary representation as follows. For example $3=(11)$, $3^2=(1001)$ which means that we let the $k$-th bit from the right be $1$ if the binary representation of this ...
3
votes
4answers
2k views

Convert from base 10 to base 5

I am having a problem converting 727(base 10) to base 5. What is the algorithm to do it? I am getting the same number when doing so: $7*10^2 + 2*10^1+7*10^0 = 727$, nothing changes. Help me figure it ...
3
votes
1answer
2k views

How do you work with the IEEE 754 32-bit floating point format?

I'm having trouble completing a question that deals with the IEEE 754 32-bit floating point format, primarily because I don't know how to use it. I was hoping someone here could clarify for me using ...
3
votes
4answers
525 views

Simple binary subtraction

$$101110 - 110111$$ Did the 2's complment and cannot get to the answer. The answer is apparently $$-1001$$ I did 2's complment on the $$110111$$ and performed addition but did not get to the ...
3
votes
2answers
89 views

How do we know $p/q$ can be expressed as a terminating fraction in base $B$ only if prime factors of $q$ are prime factors of $B$?

On cs.stackexchange I asked a math question: How to demonstrate only 4 numbers between two integers are multiples of .01 and also writable as binary. Yuval Filmus answered with a explanation ...
3
votes
2answers
192 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. ...