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

learn more… | top users | synonyms

5
votes
1answer
531 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
1answer
107 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)$ ? ...
7
votes
0answers
168 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 ...
3
votes
0answers
100 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
0answers
219 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
693 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
0answers
48 views

Upper limit for adding N numbers in grid of N processors in parallel

We must show how N binary numbers, each consisting of N bits each, can be added in a linear grid of N+logN processors. Suppose that the binary digits can be inserted directly in each processor of the ...
2
votes
0answers
207 views

Unambiguous expression for binary strings containing some substring

Is there some systematic way for finding an unambiguous expression for a binary string which contains a certain substring? For finding expressions not containing a substring, it is sometimes easy to ...
1
vote
0answers
45 views

Is there a name for this constant? (0.0100011011…)

It's the simplest number I could think of that contains any finite binary code in its digits: $$\begin{align} c &= 0.0100011011000001010011100101110111...\\ &= ...
1
vote
0answers
15 views

Given two dot products with the same vector in a prime finite field of 2 (Galois Field), how can one figure out future dot products?

I've stumbled upon an interesting "rule" derivation for the value of a dot product in $\mathbb{R}^{n}$ like this: Given an arbitrary vector $\vec a \in \mathbb{R}^{n}$ and the values of two dot ...
1
vote
0answers
83 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
1
vote
0answers
39 views

Leibniz Binary Representation of Squares

Leibniz claims to have found patterns in the square numbers and their binary representations. I cannot see any patterns at all. Here are the first ten squares and their binary representations, can ...
1
vote
0answers
51 views

Recurrence relation for Binary String Question

I have a question which has been a little stumped. I'm pretty sure I know the answer, but don't know how to prove it to be true. Here it is: "Given an infinite length random binary string, what is ...
1
vote
0answers
40 views

Is there a way to get the n-th of bits of 2^k

I have a large number N=O(2^k). For simplicity, let's say that N=n^k. However, I only need the n-th bits of N, say for example the 10-th to 16-th bit of N... without calculating the full expansion... ...
1
vote
0answers
48 views

Why is this number the smallest positive normalised binary value?

In the AQA A2 Computing textbook (Bond and Langfield, 2009), they say that this number is the smallest positive normalised value, given a 10 bit mantissa and a 6 bit exponent: ...
1
vote
0answers
86 views

Why doesn't this base 10 number x mod 2^y work for converting base 10 to binary

Okay I tried to convert 1 million to binary by dividing by a power of 2 and taking the remainder and dividing that by a power of 2 and so on and I got this: 1111010000100100000 Google says 1 million ...
1
vote
0answers
89 views

conversion of number from base 10 to base 16

I have trouble finding an example of a conversion of a number from base 10 to base 16, where there is a loss of significant digits when using the Euclidean algorithm due to division by large numbers, ...
1
vote
0answers
2k views

Calculating minimum hamming distance of a code

We use hamming code of (7,4,3); Given 4 bits of information, we'll add 3 bits of parity, and one more parity bit for the 7-bits code. Given $x_3,x_5,x_6,x_7$ $x_1 = (x_3+x_5+x_7) \mod 2$ $x_2 = ...
1
vote
0answers
30 views

How to show that the spectral radius of a binary tree approaches exp(1) as the N tends to infinity?

How can I prove mathematically that the spectral radius of a binary tree approaches e as the number of nodes tends to infinity? I mean it is true that the increase in nodes number is exponential but ...
1
vote
0answers
71 views

Probability of getting a Column full rank binary matrix

Suppose I have a $m \times n$ ($m>>n$) zero matrix (all of the elements are $0$). I want to flip $k$ ($k \ge n$ and can be controlled by the user) elements of the matrix randomly. After this ...
1
vote
0answers
222 views

Recurrent relation for number of ways to get a balanced n-binary tree

In answering a question related to binary trees, I came up with the following recurrent relation: Base cases: $$ f \left (1 \right ) = 1 $$ $$ f \left (2 \right ) = 2 $$ Recurrent relations: $$ f(n) ...
1
vote
0answers
210 views

Finding the maximum XOR metric

I'm trying to find a way to find n keys (x bits) where the XOR distance metric between them would be greatest. By XOR distance metric I just mean the value when two keys are XORed together. So for ...
1
vote
0answers
34 views

Predict binary occupancy vector from history of vectors

I have a set of binary vectors where each vector represents one day of occupancy in a house and consists of 48 elements (each element for 30 minutes of the day). Each element can be 1 meaning that ...
1
vote
0answers
102 views

Fixed decimal point numbers binary representation

I saw this formula that I cannot understand how it applies (the proof). Q: say we have a $N$ bit register (imagine a binary number with $N$ digits) for representing fixed decimal point numbers. In ...
1
vote
0answers
49 views

System of equations with binary variables

Is there any way to simplify solving system of equations, assuming that all variables are binary? All equations, however, are seen as equations with real (or, to make things simple, integer) ...
1
vote
0answers
91 views

interpret reduced cost of all binary variables

I have prepared and run a Linear Programming model in SAS. I have some questions about the output that I can’t find answers to, and am hoping that someone can help. My model contains the decision ...
1
vote
0answers
151 views

1s surpassing 0s in binary strings of odd length

Let $A(k)$ be the number of distinct binary strings of length $2k+1,$ for which the number of $1$s surpasses the number of $0$s for the first time at digit number $2k +1$, i.e., in the final digit in ...
1
vote
0answers
177 views

Recurrence relation for the digits of the integer square root in binary

I was investigating a question on the Electrical Engineering Stack Exchange site, available here: ...
0
votes
0answers
14 views

An algorithm to binary division

there is some algorithms for binary division in computer architecture. first: resorting which is described in Computer Architecture of D. Patterson second: non-resorting which is described in Computer ...
0
votes
0answers
30 views

How to prove that all powers of two minus one have only 1's when in binary representation?

It just came to my mind that all powers of two, when represented in binary format, are composed of only 1's, not 0's. I can see some logic behind it, however I can't seem to come up with an actual ...
0
votes
0answers
14 views

Give the idempotent generators of the four binary QR codes C1 , C2 , C3 , C4 , of length 7.

I'm having trouble on some homework. This is the last problem and I can't figure it out. Can anyone help or point me in the right direction? Thanks! For each code Ci , 1 ≤ i ≤ 4, from part (a), give ...
0
votes
0answers
78 views

Random walk on infinite binary tree (recurrence, transience)

Consider a random walk on the infinite binary tree with root $x$ which has the following transition probabilities. $$ p_{x,0}=p_{x,1}=\frac{1}{2},~~~p_{y,y0}=p,~~~p_{y,y1}=q,~~\text{and ...
0
votes
0answers
19 views

Convert a 6 bit binary to negative

"Explain how negative numbers are represented." My answer is that if we ie. have the number 3 and want to convert that to -3 i do as follows: 3 = 0011 in 4 bits. i switch the 1s and 0s => 1100 and ...
0
votes
0answers
11 views

Forumlate Binary Optimization problem for maximizing total net profit for terminals installed and revenue between these terminals

I need help with formulating the problem, as I am not sure if I am doing it correctly and whether there is only 1 answer or multiple correct answers. Thanks
0
votes
0answers
13 views

Estimating how many searches will be needed to justify time spent on presorting an array.

Problem Estimate how many searches will be needed to justify time spent on presorting an array of $10^3$ elements if sorting is done by merge sort and searching is done by binary search. (You may ...
0
votes
0answers
40 views

Proof by Induction for Splay Tree?

I'm preparing for an exam about Trees. One of the questions that appear in Mark Allen Weiss' "Data Structures and Algorithms Analysis in C++" is: Prove by induction that if all nodes in a splay tree ...
0
votes
0answers
21 views

Converting From Different Number Systems

I've been taught to convert from base 2 to base 10 using the following process: 10110 = $0\times1 + 1\times2 + 1\times4 + 0\times8 + 1\times16 = 0\times2^0 + 1\times2^1 + 1\times2^2 + 0\times2^3 + ...
0
votes
0answers
12 views

Redundant Binary Representation

Is it possible to have a technique using Redundant Binary Representation so that repeated addition can be obtained with no carry propagation time?
0
votes
0answers
89 views

Proving that number of codes with even weight is the same as number of codes with odd weight for a specific code book

Consider the $[n,n]$ code-book $C_0=\{0,1\}^n$ with $n$ being odd and the codes $c_i \in C_0=[c_1,c_2,...,c_{2^n}]$ being sorted in the ascending order of hamming weight (from $0$ to $n$). Now let's ...
0
votes
0answers
20 views

similarities between two binary matrices

I want to measure the similarities between two matrices A and B. Both A and B contains the feature vectors of sounds and are in binary format. i want to see what is the similarities between these two ...
0
votes
0answers
43 views

Concrete math generalized josephus recursion understanding 1.15

I am studying through the josephus problem in concrete math , Here is the equation of binary form $$f(1) = α ;$$ $$f(2n + j) = 2f(n) + β_j ,$$ $$\text{ for } j = 0, 1 \text{ and } n \geq 1$$ this ...
0
votes
0answers
31 views

Efficient way to compute the binomial using $(2^k+1)^{k+1}$

The following web page: "http://introcs.cs.princeton.edu/java/78crypto/" (at Exercise 28) effectively says that: "Pascal's triangle. One way to compute the $n$-th row of Pascal's triangle (for $n ...
0
votes
0answers
36 views

Binary division algorithm

...
0
votes
0answers
13 views

how to write a lattice $[\alpha,\beta ]$ in the form [$a,b+c\omega _7$]

$\fbox{1}$ if we write [$2-\sqrt{7},5+3\sqrt{7}$] in the form [ $a,b+c\omega _7$],what is the value of $a,b,c$ $\omega=\sqrt{7}$,since $ 7\equiv 3\mod 4$ $N(2-\sqrt{7})=4-7=-3$ $N( ...
0
votes
0answers
71 views

What is the result of the calculation: $8.375 - 0.375-0.875$?

Given the base $\beta=2$ (binary) and $t=4$ digits to represent the number in computer with hidden bit representation and symmetric rounding, what is the result of the calculation in floating point ...
0
votes
0answers
49 views

Biased form with hidden bit

A computer stores a number of 16 bits word using floating-point arrangement. Given that the first bit is reserved for the sign and followed by 6 bits for the exponent using biased form. The remaining ...
0
votes
0answers
48 views

Probability, linear independence and study of variant of Lights Out

Using Arduino, some leds and pushbuttons I've created a simple variant of the mathematically popular game "Lights Out". In my variant, the starting configuration is always all lights on; what changes ...
0
votes
0answers
33 views

Transformation of binary data

I have a function that I try to optimize using Particle Swarm Optimization. Objective function gets a binary string. So these binary strings are candidate solutions of the subject function. I can ...
0
votes
0answers
50 views

Binary String as number

For 1 ≤ i ≤ n− m, m < n, Interpreting the strings as binary numbers, we have that A[(i+ 1) ..(i+ m)] = 2 A[i..(i+ m− 1)] − (2^m−1)A[i]+ A[i+ m]. Can someone ...
0
votes
0answers
152 views

Maximum number of truths in an optimized truth table.

I have a math-related question: I have a set of predicates that need to be evaluated. These predicates can have two kinds of operators; AND/OR. When such an expression is constructed my code builds ...