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 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: ...
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
355 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
518 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
503 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
86 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
2answers
327 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 ...
8
votes
3answers
5k 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
1answer
133 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
192 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
3answers
448 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
223 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 ...
6
votes
1answer
157 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
481 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
832 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
599 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
121 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
17k 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
457 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
499 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
192 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
459 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
88 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
626 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
164 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
52 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
290 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
422 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
2answers
182 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$ ...
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
91 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
361 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
1k 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
536 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
21 views

Number of ways to choose rows with inclusion condition

I have a large collection of lists consisting of 1's and 0's, each list the same length. I call each list a row. I want to know the number of ways to select rows such that their cumulative OR results ...
4
votes
1answer
109 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
50 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
81 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
83 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
70 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
116 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
764 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 ...