Questions tagged [binary]
Questions related with (base 2) representation of numbers and their unique properties arising out of number representation.
1
vote
0answers
19 views
Primitive Factors of Mersenne numbers via Binary Programming
The problem I am considering is a general binary-programming one, but permit me to introduce it here with a specific example:
Given integer $n = 295$, find the first Mersenne number, $M_{k} = 2^{k}...
1
vote
2answers
36 views
Having trouble determining what Turing machine evaluates?
While learning about Turing machines, I've stumbled onto a problem that I'm not sure how to solve. I've put a lot of work into trying to find the solution, any help would be appreciated.
The problem ...
1
vote
3answers
33 views
Sum over the field $\mathbb{F}_{2}^{n}$
Consider the binary field $\mathbb{F}_2$ and then consider $n$ direct products of this: $\mathbb{F}_2 \times \mathbb{F}_2 \times \cdots \times \mathbb{F}_{2}$.
Hence, $\mathbb{F}_{2}^{n} = {\{x = (...
2
votes
1answer
30 views
Fourier transform on $\mathbb{Z}_{2}^{d}$
Let $\mathbb{Z}_{2}^{d} = {\{\textbf{t} = (t_1, \ldots, t_d) : t_j \in \mathbb{Z}_2}\}$.
Define the inner product on functions $f, g : \mathbb{Z}_{2}^{d} \rightarrow \mathbb{C}$ to be: $$\langle f, ...
1
vote
0answers
17 views
A question about functions from binary inputs to binary outputs
The following is a distillation of part of a larger research problem. (I have several clunky proofs for special cases, but an elegant method for the general case is somehow escaping me.)
Consider a ...
0
votes
2answers
12 views
Does the probability of occurrence of a number remain same in bit level
Say, a number x occurs with probability p.
x's binary representation be ABCD.
So, does each of A,B,C or D is set with probability p?
0
votes
1answer
18 views
Calculating the base-2 logarithm given an n-bit normalized fractional number
I recently started reading Complex Digital Circuits by Jean-Pierre Deschamps and ran into a mathematical curiosity that has stalled me on making progress.
For context, the author is describing the ...
0
votes
0answers
20 views
Binary matrix class
I am interested in searching information related to a certain class of binary matrices that accomplish all following conditions:
Upper left box (non-fixed sizes) formed by 0's
Last column in box down ...
-1
votes
1answer
32 views
binary, hexadecimal to decimal conversion.
I've one point that couldn't wrap in my mind when we talk about (binary, octal, hex) to decimal conversions?
For example, to convert binary 011 to decimal we multiply each bits starting from the LSB ...
3
votes
4answers
68 views
Is the set of points whose even binary digits are zero closed in $[0,1]$?
Let $A$ be the set of points $x$ in the unit interval $[0,1]$ that can be expressed as a binary series
$$x = \sum_{k=1}^\infty 2^{-k}d_k, \qquad d_i \in \{0,1\},$$
Such that $d_i = 0$ for each even ...
1
vote
0answers
31 views
floor instead of ceiling for log2
A colleague and myself are working out the compression factor for dictionary compressions and we came accross this site, exploring binary, in the example of converting base 10 to base 2 numbers it ...
1
vote
1answer
21 views
Maximum upper left sub-matrix with zeros by row and column permutation
I have a square matrix filled with zeros and ones and I am allowed to permute the row and column order with the same permutation for rows and columns. The goal is to find a permutation such that there ...
0
votes
1answer
39 views
Proof that $(X \mod 2^n) = X \textrm{ AND } (2^n - 1)$ for $n \geq 0$
When doing binary arithmetic, calculating the remainder of a division by a power of 2 can be done using a bitwise $\textrm{AND}$. For $n \geq 0$ we have that:
$(X \mod 2^n) = X \textrm{ AND } (2^n - ...
5
votes
1answer
43 views
binary search tree with key values $ a_1 < \dots < a_k$. How do I choose $j$ to still get a tree with minimal height?
So at the beginning I have an empty binary search tree. Moreover I have key values $a_1 < \dots < a_k$. How can we choose $j$ so that after the first insert of an element with key value $a_j$ a ...
0
votes
0answers
26 views
Expressing binary length of ternary sequence
I have a problem with expressing binary length of ternary sequence. One of the questions at tutorial sheet from algorithmics specified a question, which can be simplified to a below problem:
We have ...
0
votes
1answer
30 views
Find the binary of decimal numbers given with powers of 10 [closed]
Convert to binary : 46.5 * 10^(-24)
Or something like 46.5 * 10^(24)
I have to find the binary equivalents here, for the purpose of representation in IEEE 754 floating point representation. But I ...
0
votes
0answers
11 views
Linearization of constraints including product of binary variables.
I have three constraints including product of binary variables as following:
enter image description here
So basically, I have a complicated multiplication of binary variables. I am wondering if I ...
3
votes
1answer
60 views
Cycles in bit-limited verson of Collatz map
By 'bit-limited', I mean that we have a computer/calculator that handles binary numbers up to $n$ bits ($n>=1$), and any numbers greater than $2^n-1$ overflow by truncating the higher bits. ...
0
votes
0answers
13 views
How to properly write the conditional probability distribution when talking about existence of a random variable?
I am writing a paper and I want to describe the following conditional distribution in an equation.
Suppose that we have a binary variable $X$ and a random variable $Y$. Conditioned on $Y = y$, ...
2
votes
0answers
30 views
Cycle length of K-ary Boolean function
Boolean networks have been extensively studied, however I didn't find a reference to the following problem. May be you can provide one, or give hints to a possible solution.
Define K Boolean ...
1
vote
0answers
25 views
Converting a number to IEEE 754 - Problem [closed]
I am trying to convert -12.5 to the IEEE754 single precision (32bit) format. I use this tutorial https://youtu.be/8afbTaA-gOQ?t=105. At the time stamp linked she converts the fraction part to binary. ...
0
votes
0answers
13 views
Determine the set of integers that are represented by the binary quadratic form (1,0,-1) [duplicate]
I need help with finding the set of integers represented by the form (1,0,-1).
This is essentially f(x,y) = x^2 - y^2 which can be factorised into (x + y)(x - y) and the determinant is d = 4 > 0.
0
votes
2answers
73 views
How many times does the binary digit $1$ appear in numbers $0$ to $255$?
I am trying to find an easy way to calculate the number of times that the digit "$1$" appears in numbers $0-255$ (in the binary system). I consider the answer must be a power of $2$ since $256 = 2^8$ ...
0
votes
1answer
37 views
Proof of equivalence between two methods of binary to decimal conversion.
I have two binary to decimal conversion methods and want a proof - or an intuition at least - of why they are equivalent.
The first method is quite intuitive to me and seems to be more popular:
$[...
0
votes
1answer
16 views
Two's complements
Calculate 111000_2 - 1100111_2 and convert the result into a 8-Bit two's complement.
My suggestion:
I'm inverting 1100111_2 into 0011000_2 and add +1, so the result would be: 0011001_2.
Then I'm ...
0
votes
1answer
40 views
Optimization over a binary (or discrete) variable
I have the equation $y=Kx$ where, for example, $x=\begin{pmatrix} x_1 \\ \vdots \\ x_{50} \end{pmatrix}$, where $x_i=0$ or $1$
$K \in M _{1000,50}(\mathbb R)$ a given constant matrix and $$y=\begin{...
3
votes
1answer
45 views
Can we write $2^\alpha$ as sum of smaller 2-powers when $\alpha\geqslant 5$ is a positive integer?
Let $\alpha$ be a positive integer $\geqslant 5$. Let us consider
\begin{align*}
&B_1\subseteq \{0,1,2,3,4\}\\
&B_2\subseteq \mathbb{N}-\{0,1,2,3,4\}
\end{align*}
where $B_2$ can be finite or ...
0
votes
1answer
43 views
I need to solve one equation, but I dont know how to solve equation with floor functions
Im a student with not such a knowledge to solve equations with floor functions. I want to ask, if it is even possible and if it so, how is possible to prove this equation to be true.
...
0
votes
0answers
39 views
24-bit Binary to single precision floating point number
I have the 24-bit binary:
0101 0011 1111 1101 0111 1101
And I need to figure out:
What pair of single precision floating point (real) numbers could be represented by these 24-bits?
I'm fairly ...
0
votes
0answers
67 views
Proof of the duality principle in Boolean Algebra
I have looked at some proofs of the duality principle online, and those use a lot of algebra which I do not understand.
Is there a simple proof of the duality principle? I know the basic laws, ...
1
vote
2answers
63 views
Generating function for special string 11100
Let $S$ be the set of $\{0,1\}$-strings that do not contain $11100$ as a string. Find the generating function of S where the weight of a string is its length.
I tried this way :
Consider all blocks ...
1
vote
2answers
55 views
Are there any non-trivial examples of this decimal-binary property
My birthday is 10th of October or 1010 in MMDD format.
I just realized that 1010 contains two copies of the number 10 and if spelled out in binary,
$1010_2=10$
I was wondering how many other ...
-1
votes
1answer
37 views
Is the dimension of a binary linear code the number of codewords it contains? [closed]
For example, would the dimension of the binary linear code $\{0000,1111\}$ be $2$?
1
vote
1answer
35 views
Finding similarities between binary strings
I have been tasked with this puzzle for my programming class, it's purely a puzzle and doesn't count towards any grades, but not being able to solve it is really bugging me!
We have been given two ...
1
vote
1answer
26 views
Prove that the mapping of a number to its XOR with some constant c is bijective
Prove that $x \mapsto x \oplus c$ is a bijection over the range $[0, b]$, regardless of the value of constant $c$, where $b = 2^{k} - 1, k \in I^{+}$.
0
votes
0answers
23 views
Understanding Weird Relationship Between Hamming Weights
I have two binary "mapping" matrices $\delta_0$ and $\delta_1$
$
\delta_0 =
\begin{bmatrix}
1 0 1 0 0 0 0 0\\
1 1 0 1 1 1 1 0\\
0 0 0 0 1 1 0 0\\
0 1 1 1 0 0 0 0\\
0 1 1 0 1 0 0 0\\
1 0 0 1 1 1 0 0\...
2
votes
0answers
110 views
What is known about evil primes?
An evil number is a positive integer $n$ that has an even number of $1$s in its binary expansion. Many theorems exist about evil numbers, the most known ones are probably those that involve the Thue-...
1
vote
1answer
52 views
Prove that for every $n$, the binary representation of $n + 1$ contains exactly one bit that flips from $0$ to $1$
I know since $n$ is a binary representation it can be represented $ \sum_{i = 0}^{p}b_{i}\cdot 2^{i}$, where $b_{i}\in \{0,1\}.$
I have the intuition for this problem, i think. If $n$ is odd then the ...
-1
votes
1answer
54 views
Distance of binary strings to produce the lexicographical order
Indexing objects like elements of a Cantor Set or nodes of a Binary Tree can result in a enconding system of binary strings like illustrated bellow:
The illustrated indexes form a finite set, $$C_3=\...
0
votes
0answers
41 views
Rank of two binary matrices
Let $N=2^n$. Consider two matrices $M,P$ over $GF(2)$ where $M$ is a circulant matrix of size $(N,N)$. Matrix $P$ is of size $(N,N+1)$. All values of $P$ are same as $M$ except last column. Also $P_{1,...
0
votes
1answer
30 views
How to choose a set of boolean functions with a specified probability of getting a 1
So let's say I have a boolean function $f(x)$ that takes in a size k binary vector and outputs a binary scalar. Each function is defined as a $2^k$ vector. For example $f((0,0)) = 0, f((0,1)) = 1, f((...
0
votes
0answers
43 views
Proving by induction of binary number.
If n is binary represented natural number, P(n) for some predicate P.
This is just a sample question I made.
Base case) Let n = 0.
This is divisible by 2
Induction step) Let n = k is a binary ...
0
votes
2answers
34 views
Converting Large Decimal Numbers to Octal and Binary
I have large numbers that I need to convert to Octal and Binary systems. Examples of numbers that I am working with are $10^{10}$, $10^{20}$, $10^{30}$ ... (powers of 10) and numbers that are ...
1
vote
0answers
25 views
Need to clarify 1 / LN(2) in binary representation
I want to represent 1/LN(2), 1.442695041 in 32 bits binary. I found that must be 1.0111000101010100011101100101001, but a work collegue insists it needs to be shifted right and add an integer of "1", ...
0
votes
0answers
35 views
Determine whether an integer can be constructed from other integers by applying bitwise AND and OR operations
Given binary numbers $b_1, b_2, ... , b_m < 2^n$ as well as their complements $b'_1, b'_2, ..., b'_m$ (with leading $1$'s if necessary, such that $b_i + b'_i = 2^n - 1$), is it possible to quickly ...
1
vote
1answer
34 views
How to find shorter encoding of $256$ bit number
Wondering if you could encode a number such as $2^{256}$, as a polynomial equation or some other encoding that would make it shorter than its actual value written out in decimal notation which is ~70 ...
0
votes
0answers
31 views
Solving for a and b from xor and difference
Can we solve for a and b, from
$a-b = x$
$a \oplus b = y$
Even when x and y can be negative?
I tried substituting the value of a in xor equation from the ...
0
votes
1answer
29 views
How to detect if binary number divides by 3 if transmitted MSB first
How to detect if a sequence of bits, transmitted MSB first, divides by 3 ?
The FSM in below question solves the problem if LSB first. FSM doesn't seem to work because adding '0' bit to left of number ...
0
votes
1answer
30 views
How to calculate binary tree node number and layer number generated from $10^{100}$
Trying to learn about calculations related to binary trees, and would like to know how many binary tree node layers there are in a binary tree generated from $10^{100}$, and more generally, how to ...
0
votes
1answer
50 views
If you can cram any more than $2^n$ unique, obtainable values into a binary string [closed]
When you typically talk about binary strings, you basically say that they have $2^n$ values. So 10 is 2, 11111111 is 255, etc.
...
