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 ...
18
votes
8answers
7k 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?
18
votes
4answers
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: ...
17
votes
4answers
574 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 ...
13
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 ...
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
2answers
27k 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?
11
votes
1answer
569 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
2answers
370 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
535 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: ...
9
votes
0answers
216 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 ...
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
94 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
1answer
174 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
3answers
593 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
412 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
2answers
592 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 ...
6
votes
1answer
176 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
628 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
80 views

Tzaloa 2015 game problem (piles with $1,2,4 \dots 2^{19}$ coins each)

We have $20$ piles with $1,2,4,8\dots 2^{19}$ coins repectively and two players. In each turn a player must select five piles that have at least one coin and remove exactly one coin from each. Player ...
6
votes
1answer
1k 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
603 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
7answers
640 views

How to find the unique sums in the values 1,2,4,8,16, 32

I apologize but I'm not sure what you would even call this problem. I have some data that provide a numeric code for race as follows: hispanic(1) + american_indian_or_alaska_native(2) + asian(4) + ...
5
votes
5answers
409 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
733 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. ...
5
votes
2answers
716 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
603 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
232 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
97 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
800 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
198 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
58 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. ...
5
votes
3answers
11k 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. ...
4
votes
3answers
355 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
3k 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
529 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
204 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
2answers
918 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 ...
4
votes
1answer
4k 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
511 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
385 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
4answers
8k 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
2answers
2k views

Terminating decimal number which is not terminating in binary

I know that when converting a decimal number from base 10 to base 2, the result might be not terminating, even though the number is terminating in base 10. For instance, 0.2 -> 0.0011 0011 0011 ... ...
4
votes
1answer
14k 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 ...
4
votes
2answers
102 views

Integers with consecutive nonzero digits in base 2

Note that $2016=11111100000$. How many integers $\le n$ have their nonzero bits consecutive in their binary (base $2$) expansion? The case $n=2^m-1$ is easy. The question is about a closed formula for ...
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
1answer
623 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
2answers
52 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. ...
4
votes
2answers
96 views

Switch flipping sequence with no repeats

Okay, you have N switches. They are all off. You may flip one switch at a time. You must visit each possible state of switches being flipped without repeating any state. At the end, you must be ...