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

learn more… | top users | synonyms

31
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 ...
18
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
3k 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
981 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
1answer
490 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
475 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
3answers
2k 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. ...
8
votes
2answers
82 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 ...
7
votes
2answers
1k 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 ...
7
votes
1answer
162 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
122 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
173 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
2answers
393 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 ...
5
votes
10answers
596 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
2answers
334 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
1answer
356 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
180 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
340 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
490 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
162 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
575 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) ...
4
votes
3answers
274 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
12k 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?
4
votes
2answers
1k 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
300 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
2k 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
348 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
2answers
75 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 ...
4
votes
1answer
862 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
1answer
288 views

A question dealing with residual codes.

I've been reading about residual codes, and have come across several statements that I am having trouble showing. (1.) By using the residual code, one can show that a $[16, 5, 8]$ binary code ...
4
votes
1answer
460 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
43 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
59 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
78 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
1answer
111 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
699 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
922 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
4answers
468 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
80 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
99 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. ...
3
votes
2answers
164 views

Finite bit strings that do not contain '$00$'

I am studying for an exam and I am having trouble with this practice question: In this question, we consider finite bit strings that do not contain $00$. Examples of such bitstrings are $0101010101$ ...
3
votes
3answers
2k views

A proof that powers of two cannot be expressed as the sum of multiple consecutive positive integers that uses binary representations?

In this earlier question, the OP asks for a proof of the statement Every natural number not of the form $2^k$ for some natural number k can be written as the sum of two or more consecutive ...
3
votes
2answers
116 views

How many binary sequences of length n are there that contain exactly m occurrences of the pattern 01?

I thought there were n-1 places between the first and last digit. In these places I hypothesized there are switches that change (from 0->1 or 1->0) For ...
3
votes
2answers
165 views

Binary Sequence Block

More of an informatics question, rather than applied mathematics - Source - Zonal Informatics Olympiad 2011 Question Paper Although, I've tried a few brute methods, I haven't really understood ...
3
votes
1answer
8k views

Calculating CRC by long division: How to decide the top number of long division?

Ok, I know how to use long division by using regular numbers, but when comes to binary numbers I'm getting confused. In following calculation I can see the equation solved but I don't understand ...
3
votes
2answers
34 views

Classification of numbers on the base of binary representation

The problem is the following. I would like to find a simple algorithm or principle of classification of numbers regarding their presentation in binary form. Let's consider an example. The numbers by ...
3
votes
2answers
94 views

Recognize a valid binary Golay codeword

Are there any properties of a binary [24,12,8] Golay code which would allow me to say, for example, that a given 24-bit word is or is not a Golay codeword for some generator matrix? That is to say, is ...
3
votes
4answers
4k 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 ...
3
votes
2answers
38 views

Why are these two conversion methods (base 10 to base 2) equivalent

I've come across two methods for converting a base 10 number into its base 2 equivalent. I want to know why they are equivalent. Method 1: We're given a number $N$ to convert into binary 1) Find the ...