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

learn more… | top users | synonyms

28
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 ...
14
votes
8answers
2k 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?
10
votes
1answer
459 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
444 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
79 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
109 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
2answers
311 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
589 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
258 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
281 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
2answers
302 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
1answer
166 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
371 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
122 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 ...
4
votes
3answers
251 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
3answers
234 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
336 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
754 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
244 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
413 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
48 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
75 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
103 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)$ ? ...
3
votes
2answers
8k 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?
3
votes
4answers
366 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
76 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
54 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
149 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
149 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
6k 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
51 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 ...
3
votes
2answers
77 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
1answer
101 views

Lower bound on a number theoretic function

Let $n$ be a positive odd integer, let $$n_j = \Bigl\{\frac{n}{2^{j+1}}\Bigr\}\,,$$ where $\{x\}$ denotes the fractional part of $x$, and finally let $k = \lceil \log_2 n\rceil$. Consider the ...
3
votes
1answer
64 views

q-ary code/Latin squares

For any value of $q$ the largest number of elements in any q-ary code $C$ of length $4$, distance $3$ is $q^2$. How can we prove that this is attainable iff there are a pair of mutually orthogonal ...
3
votes
1answer
285 views

On a scale of 1 to 10, how likely is it that this question is using binary? [closed]

I just read this interesting xkcd strip: At first I thought it was funny, but as I got to ruminate a little over it, I was surprised to be unable to find an answer. As Karolis Juodelė pointed out, ...
3
votes
1answer
73 views

comparing bit lengths of binary numbers

Suppose I have two binary numbers x and y that have bit lengths of nx and ...
3
votes
1answer
66 views

How to take one's complement of a positive integer?

Of course we can do that by converting the number to binary and then converting it back to decimal, but to do that directly in decimal?
3
votes
1answer
70 views

Find the solutions of Boolean equations

It's given 4 Boolean equations. I need to find the number of solutions of each. $a)\ x_{1}x_{2}\oplus x_{2}x_{3}\oplus\ ...\ \oplus\ x_{n-1}x_{n}=1$ $b)\ x_{1}x_{2}\vee x_{2}x_{3}\vee\ ...\ \vee\ ...
3
votes
0answers
70 views

Number of 'unique' one bit binary functions with N-bit inputs

Consider the set of binary functions that takes an N-bit input -> 1 bit output. There are 2^(2^N) elements in this set. Now potentially reduce this set by restricting to only considering functions ...
3
votes
1answer
159 views

Fast fourier transforms of random binary data

I am a physicist who is trying to make sense of FFTs and binary data. Say I have a series of random binary data, which is measured with a repetition rate of 400Hz (interval time of 0.0025s). I have a ...
3
votes
0answers
205 views

An Upper Bound for an $[n,k,d]$ Linear Binary Code.

I've been reading about the various upper bounds for different types of codes. Recently, I came across a statement that is similar to the Singleton Upper Bound that I am having trouble proving. The ...
3
votes
0answers
664 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 ...
2
votes
4answers
728 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 ...
2
votes
2answers
844 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. ...
2
votes
2answers
95 views

Twos complement notation question?

I have a quick question how do you do the two complement system, For example say I have in two complement a $6$ which is $0110$ and $3$ which is $0011$ and I want to add $6+(-3)$ I know what five is ...
2
votes
2answers
67 views

What is the relation between this binary number with no two 1 side by side and fibonacci sequence?

I saw this pattern of binary numbers with constraints first number should be 1 , and two 1's cannot be side by side. Now as an example ...
2
votes
3answers
100 views

Finding element in binary representation of $GF(2^6)$

I got the following task: Let $F = GF(2^6 )$ be K[x] modulo the primitive polynomial $h(x) = 1 +x ^2 +x ^3 +x ^5 +x ^6$ , and let $\alpha$ be the class of x. I have a table with the binary ...