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

learn more… | top users | synonyms

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
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 ...
2
votes
1answer
62 views

Count 1-bit in binary integers

Given an integer range [A,B], (1) What’s the probability to get a 1-bit if we first randomly choose a number x in the range and then randomly choose a bit from x? (2) What’s the expected number of ...
2
votes
1answer
41 views

Computation and Elimination (Solution Verification)

Consider a set B (of binary strings) given by the introduction rules: \begin{equation} \frac{}{\epsilon :B} \quad \frac{a:B}{s_{0}(a):B} \quad \frac{a:B}{s_{1}(a):B}\end{equation} ...
2
votes
1answer
368 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) ...
1
vote
1answer
32 views

Number of Positive Definite Binary Matrices

How may positive definite matrices (over finite field- $F_p$) are possible? What is the criterion in getting those?
1
vote
1answer
32 views

Distance measures for binary data

I was wondering what are some good distance measures for binary data that have the following properties. I know that there are measures like the Jaccard index and the Dice Index, but they don't ...
1
vote
1answer
89 views

The maximum number of digits in binary multiplication

Given 2 binary numbers of n digits. (n can be from 1 to something large) What is the maximum number of digits of their product? I think it's 1 in 1-digit*1-digit, and 2n otherwise. But I want some ...
1
vote
1answer
187 views

Solving a constrained Lagrangian dual problem

Consider the following $\max-\min$ integer programming formulation expressed in the binary decision variable $\mathbf{z}$: $$\begin{align*} \max&m \\ s.t.&\\ m \leq& s_i + \sum_j^J ...
1
vote
1answer
78 views

Minimizing deviations from threshold value from a given group of numbers

Given a set of numbers $a_n$, a threshold level $t$, how do I find the combination of numbers that will sum to at least the threshold with minimum deviation? Added: That is, they must always exceed ...
1
vote
1answer
156 views

Determining the position of a binary value with $k$ one bits and $n-k$ zeros in an enumeration of $C_k^n$ bit strings

I first enumerate a list of all possible binary strings for a length $n$ (e.g., ["00", "01", "10", "11"] for $n=4$). This leads to a list of $2^n$ binary strings. Within that list of $2^n$ elements, ...
1
vote
1answer
137 views

Problem about BCH code

I have another homework to do, please give me some hints in order to solve this problem: "Determine whether the dual of an arbitrary BCH code is a BCH code."
1
vote
1answer
76 views

How to convert these numbers?

I am trying to understand number systems: (binary and decimal) How can I convert the following numbers using the least amount of digits: $(47)\text{base}-10$ to signed binary. $(-27)\text{base}-10$ ...
0
votes
1answer
29 views

Having problem with 10's complement subtraction

From what I've found, to find A - B using 10's complement; where A and B are decimals Let A = 215 , B = 155 Find 10's complement of B = (1000 - 155) = 845 Add 10’s complement of B to A If it ...
0
votes
1answer
29 views

Absolute and relative error of a binary number?

Given is the following system $A:={ \pm 1.a_1 a_2 a_3 a_4 \cdot 2^e}$, $a_{i}\in \left \{ 0,1 \right \}$, $i\in \left \{ 1,2,3,4 \right \}$, $e\in \left \{ -8,\ldots,8 \right \}$. Find the absolute ...
0
votes
1answer
28 views

Binary expansion

I am trying to get my head around the left and right shift for binary expansion. The rules are: Shifting to the right ...
3
votes
0answers
68 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
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
659 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
46 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
174 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
41 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
34 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
24 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
65 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
84 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
862 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
27 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
61 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
193 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
142 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
33 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
89 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
46 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
81 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
135 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
162 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
25 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
24 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
30 views

Binary division algorithm

...
0
votes
0answers
12 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
42 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
40 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
32 views

Search L leaves smaller than node N

So in my binary $kd$-tree I have a node $N$. Now I search for the number of leafs $L$ "on the left" side of $N$ (this includes the left child branch of $N$ and all parents where the node is a right ...
0
votes
0answers
62 views

What is the number theory behind this?

I am given $3^{1000}$ and asked to find, in base $2$, now many digits it takes to represent this number. According to Wolfram, it is $1585$, but I don't know why. I understand that $2^n$ would be ...
0
votes
0answers
238 views

Prove that $gx^2 \sim f$

Let $f(x,y) = ax^2 + bxy + cy^2$ be a positive semidefinite quadratic form with determinant $= 0$. Let $\operatorname{gcd}(a,b,c) = g$. Show that $gx^2 \sim f$. I'm not sure how to do this. All I ...
0
votes
0answers
39 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
31 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
49 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
131 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 ...