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
154 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
58 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
344 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
30 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
82 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
185 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
77 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
136 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
75 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$ ...
3
votes
0answers
61 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
202 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
654 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
45 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
170 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
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
23 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
61 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
83 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
751 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
26 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
182 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
127 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
32 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
86 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
45 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
79 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
134 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
158 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
17 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
12 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
0answers
16 views

Binary: Two Compliment with decimal point

Good Day sir/mam, Im trying to figure out how to do the two's compliment binary to decimal with decimal points or fraction. I have this problem of 138.375 - 225.75 = -87.375 and If I'm right: ...
0
votes
0answers
27 views

Perform this arthimetric operation on 8bits 2's complement numbers..

So the question is: Perform the given arithmetic operation on the following pairs of 8-bit 2’s complement numbers. In each case, indicate whether or not overflow occurs. the numbers: 11010100 + ...
0
votes
0answers
22 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
11 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
25 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 ...
0
votes
0answers
41 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
33 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
237 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
187 views

how to find power of binary number where base and power both are binary?

if one have to find power to binary number by rising power of binary number eg: 101^011 (5^3=125) how to find it without converting it to decimal number. means i want to give input as 101^011 and get ...
0
votes
0answers
28 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
48 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
129 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 ...