Questions tagged [binary]
Questions related with (base 2) representation of numbers and their unique properties arising out of number representation.
1,555
questions
-2
votes
0
answers
38
views
How can I tell which is closer to 0.72 without converting the binary numbers to decimal? [closed]
If I have two binary floats:
$0.10111000_2$ and $0.10111001_2$
How can I tell which is closer to 0.72 without converting the binary numbers to decimal (base 10)?
0
votes
1
answer
35
views
Arranging Binaries!
Today I was working on a problem, for which I think there are two possible answers to it,
the question is we need to Arrange five $0$'s and five $1$'s such that no two $0$'s come together and no two 1'...
- 19
1
vote
0
answers
21
views
Max edit distance between binary strings of length n
Given a binary string s of length $n>2$.An edit operation is a single character insert, delete or substitution. The edit distance between two strings is the minimum number of edit operations needed ...
- 11
-1
votes
1
answer
34
views
Number of ones in the dyadic expansion of m [closed]
I was going through a paper where I stuck on a combinatorial argument as follows
I want help with the first assertion i.e proving the inequality $\alpha(m+l)\le\alpha(m)$.
As the author suggests it is ...
- 1,660
1
vote
0
answers
18
views
Distributions for bit flipping experiment: N bits, probability of flip is p [closed]
N - number of total bits
p - probability a bit flips
a - number of bits that are currently 0(zero)
The experiment is as follows
The bits start all zero
Each round, each bit flips (or not) according ...
- 119
-1
votes
2
answers
92
views
Can every number be written as $2^{a_1}+\cdots+2^{a_n} + 1$?
I am reading an algorithm that calculates $x^y$. Basically it is about an implementation of a function $power(x, y)$ where $x$ is the base and $y$ is the exponent i.e. the power.
The algorithm uses ...
- 1,527
1
vote
0
answers
16
views
Computing inverse elements of symbolic matrices with binary variables
I'm working with symmetric, symbolic matrices $A$ with real coefficients and linear binary variables like
$$
A = \begin{pmatrix} 0.5x_0 & 0.3x_1+0.002x_2 & 0 & 0 \\
0....
- 11
0
votes
1
answer
68
views
How can I find the least amount of place checks required to determine if a binary number in a range is equal to a specific value?
For some G and N, there exists an optimal function/algorithm in the domain [0, G] which can decide if its argument is equal to N by checking the value of only V binary digits. Given G and N, how can I ...
- 123
0
votes
1
answer
32
views
Binary variable notation
Suppose we have a memory element, i.e., a Flip Flop ($FF$).
A $FF$ can have a current value of binary $0$ or $1$, i.e., $FF \in \{0, 1\}$.
Is there any formal way to represent three types of $FF$s:
if ...
- 1
0
votes
0
answers
25
views
How does shifting a binary number to the left translate to its hexadecimal representation?
So I have a binary output that is represented in Hex that I need to format it's binary representation in a certain way.
Say I have a binary output of: 000110111001 or 0x01B9 in HEX. I want to add 1 ...
- 33
-9
votes
1
answer
514
views
Generating function for a given sequence [closed]
Given a sequence (10000 first members), I need either construct a generating function or find simple method to check if any arbitrary number belongs to this sequence.
...
2
votes
0
answers
84
views
Does ADMM promise to converge if there are binary variables in each agent's constraints?
As is stated in chapter 9 of Boyd et al.1, ADMM can be used as a heuristic method for solving non-convex problems.
Here, my case contains binary variables and it is more special since the binary ...
- 31
1
vote
2
answers
45
views
Number of ways to break up consecutive series of $1$s in binary number
There is a binary number of length $N$ which consists of a consecutive series of 1s. For example, if $N=5$ the number is $11111$. How many ways are there to intervene on this number (i.e., replacing $...
- 501
2
votes
0
answers
44
views
Do bitwise rotations and increments modulo $2^n$ generate the symmetric group?
Let's say we have two operations we can perform on a binary number of length $n$:
Right-rotation, where the most significant bit is taken off and inserted in the one's place, pushing all other digits ...
- 521
1
vote
1
answer
133
views
formula for the position of the ith one and the ith zero in an infinite binary sequence
Define an infinite binary sequence as follows: start with 0 and repeatedly replace each 0 by $001$ and each $1$ by $0$.
Provide, with proof, a formula for the positions of the nth one and a formula ...
- 883
0
votes
1
answer
58
views
Regular Expression - binary digits, no occurrences of 111, solving methodology?
Can someone show in some simple steps how one goes about creating a regular expression from binary digits that excludes all occurrences of 111? What I am having trouble is how one starts these sorts ...
1
vote
1
answer
47
views
How to prove that binary representation of number always has more digits than base 10 representation?
I understand the idea intuitively that because the number of options for each digit is more "granular" for base $2$, we need more digits to represent the same number as opposed to base $10$.
...
- 142
1
vote
2
answers
46
views
What is this set representation of binary numbers called, when the set elements are positions where the digit are 1?
Say I have $b = 010010$, then the set $S = \{2,5\}$ represents $b$ by marking positions where the digit is $1$. Is there a name for this representation? How would I go about formally writing a ...
- 683
4
votes
1
answer
132
views
formulas for binary expansion of irrational number between $0$ and $1$
One can write any irrational number between $0$ and $1$ composed as closed expression of popular known numbers, such as, for example, the expression $$\frac{1}{\sqrt{2}}$$ in binary by successively ...
0
votes
0
answers
42
views
Writing uniqueness binary expansions
I'm reading a solution to a problem that I don't fully understand. The statement writes out the binary expansion of a real number and requires that there is no natural number $N$ beyond which the ...
- 1,184
0
votes
0
answers
24
views
Decimal analogue to boolean AND operator?
I am looking for a way of expressing something like:
$\sum{a_k} \sum{b_k}, \, a_k \in \mathbb{R}, \, b_k \in \mathbb{R} \tag{1}$
with the caveat that I would like the result to be negative in the case ...
- 143
0
votes
0
answers
11
views
Is there a prior for not-all-zero multivariate binary vector? [Bayesian]
For each individual $i = 1, \ldots, N$, we observe a multivariate binary response vector of $J$ items $Y_{i} \in \{0, 1\}^J$. For each item $j$, we have a vector of covariate $x_{ij}$. Assuming that ...
- 1
0
votes
1
answer
22
views
Missing sequence number problem solved with XOR
I'm trying to understand how the XOR operation managed to solve the problem PermMissingElem
I know one of the properties of XOR is that:
...
- 105
0
votes
2
answers
41
views
Converting binary to hexadecimal and octal
I’ve noticed a grouping method when converting from binary to hexadecimal and binary to octal.
When converting from binary to octal, my math book says to group the binary numbers into groups of three, ...
0
votes
0
answers
23
views
Comparing distributions of binary valued vectors: covariance matrix is enough?
Say we have two discrete distributions, $\vec{y}\sim p_y$ and $\vec{x}\sim p_x$, for both of which, data vectors have binary-valued entries: $\vec{y}\in\{0,1\}^n$ $\vec{x}\in\{0,1\}^n$, where $n$ is ...
- 75
1
vote
0
answers
70
views
$0<a_1<a_2<\cdots<a_k$ satisfy $\bigoplus\limits_{i=1}^ka_i = 2^n-1$ ($\oplus$ represents bitwise or) prove |config number of k is even - odd| =1
In a finite set $S$ with $|S|=n$, let $N_n^k$ be the number of ascending chains of $k$ nonvoid subsets $\emptyset \ne S_1 \subsetneq S_2 \subsetneq \cdots \subsetneq S_k$ with strict inclusion such ...
- 11
1
vote
1
answer
34
views
I am very confused about this question can someone please help me solve it. Thanks!
Lucy works in the space $\mathbb{R}^n$ of vectors $x = [x_1, . . . , x_n]^T$ . Chris chosen a different basis and handles vectors $x’ = [x’_1 , . . . , x’_n ]^T$ , where $x$ and $x’$ are related by $...
0
votes
3
answers
109
views
Powers of 3 in binary - how can you prove this evidency?
Prove that the number of 1s in the powers of 3 binary representation is (on the whole) increasing.
$3^0=1_2$ (number of 1s=1),
$3^1=11_2$ (number of 1s=2),
$3^2=1001_2$ (...
2
votes
0
answers
104
views
Reversing a complex boolean function
I am trying to reverse-engineer the DRAM address function of a memory controller. This is a function that maps a physical address to a DRAM bank.
More formally, I am trying to find functions $f_i$ for ...
- 71
1
vote
1
answer
24
views
What algorithm is used to compute a “bit that is two places to left of least significant bit in binary expansion of $n$” in the OEIS sequence A086483?
Let $Q$ denote the sequence A086483:
Bit that is two places to left of least significant bit in binary expansion of n.
For n = 4, 5, 6, 7, 8 the binary expansions are 100, 101, 110, 111, 1000 and the ...
- 740
1
vote
1
answer
38
views
Is this a total ordering of the set of full labelled binary trees? [closed]
Consider a binary tree labelled by some ordered set of letters. Traversing the tree in preorder determines a sequence of letters - a word.
A binary tree is called full if all its non-leaf vertices ...
- 316
0
votes
0
answers
23
views
Mathematically calculate Bit Rotation
I am trying to calculate a cyclic bit rotation mathematically, but I am trying to avoid the use of mod operators, is there a way to do this,
This is what I have written so far
...
0
votes
2
answers
44
views
Exact number representation to represent time from $1$ nanosecond (ns) to $1000$ seconds (sec)
I need help figuring out the exact number representation to represent time from $1$ nanosecond (ns) to $1000$ seconds (sec) with an accuracy of $1\%$. I know a floating-point is preferred over a fixed ...
- 341
1
vote
1
answer
53
views
Prove Inequality for Full Trees
TLDR
I'm seeking a proof for the following claim:
Let $T$ be any full tree of degree $n$. Let $m$ be the total number of nodes in $T$, and let $r$ be the number of regular nodes. Then $m > n \...
- 111
-4
votes
1
answer
70
views
Difference between binary division and its decimal division [closed]
Suppose I have one decimal number $23$ which decimal representations is $10111.$ Now $10111$ treated as dividend and divisor is $3$ which binary representations is $11.$ When $10111$ is divided by $11$...
- 1
3
votes
1
answer
93
views
Help identify this pairing function
I'm organising the natural numbers in columns like this, based on the number of $1$ bits contained in the binary expansion:
1
11
111
1111
11111
111111
1111111
11111111
10
101
1011
10111
101111
...
- 257
0
votes
2
answers
40
views
Sharing (binary substrings vs. mathematical property)?
Do the natural numbers whose binary (representations) strings share the same particular binary substring also share any mathematical property? One obvious example: when a single one-bit substring in ...
1
vote
1
answer
82
views
Find minimum moves to transform one number to another
Suppose we are given two positive integers, $a$ and $b$. Each move we are allowed to divide $a$ by 2 (but only if $a$ is even), multiply $a$ by 2, or add 1 to $a$. How many moves does it take to ...
- 163
1
vote
1
answer
68
views
Proving that the desired set exists
Let $n_2$ be the binary form of $n\in\mathbb N$. Define the function $F$ on $\mathbb N\times \mathbb N \to \{0,1\}$ by $F(n,i)=1$ if $i$ is less than the length of $n_2$ and the $(i+1)$th digit (...
- 10.9k
0
votes
1
answer
21
views
Is the height of this recursive tree $\lceil \log _{2} n \rceil$?
I adapted the following code for a recursive binary cumulative sum function in Python:
...
- 97
0
votes
0
answers
45
views
How to know number of elements on a level in a complete binary search tree mathematically?
So I was thinking if it's possible to know how many nodes exist on a particular binary tree level mathematically.
I came with the formula (where $n$ is the level):
$$2^{n-1}$$
But I didn't consider ...
- 15
3
votes
1
answer
77
views
When will the algorithm stop. While $a>0$, do if $a<b$ then $(a,b)\rightarrow (2a,b-a)$ else $(a,b)\rightarrow (a-b,2b)$
I came to this question in the Problem Solving Strategies.
We start with the state $(a,b)$ where $a,b$ are positive integers. To this initial sate we apply the following algoritm
While $a>0$, do if ...
- 31
1
vote
2
answers
91
views
How does the $2$'s complement describe a negative number in binary?
According to my knowledge, the 2's complement is used to describe a negative number in binary representation. But I have this confusion.
Example: Suppose that we are using 5 bits registers. The ...
- 11
0
votes
1
answer
40
views
How to calculate orders of magnitude using a new base?
I am trying to think of a different way to encode time in software (for a fantasy world), and am currently imagining starting from the second and going up in -- I don't know what to call it -- "...
- 3,166
2
votes
1
answer
70
views
Does there exist a relationship between logarithms and the corresponding base number system?
I like to think of logarithms this way: $\log_a(N)=y$ implies that, the a denotes the power at which you're expanding / shrinking, the N represents the size of you after y units of time has passed.
...
- 57
0
votes
1
answer
36
views
How to demonstrate the method used to convert decimal to any other base?
Let's say we have an arbitrary number in base $b$, $(x_3x_2x_1x_0)_b$.
We can write the equivalent of this number in base $10$ as follows:
$(x_3x_2x_1x_0)_b = x_3*b^3+x_2*b^2+x_1*b^1+x_0*b^0$
So, let $...
- 23
0
votes
0
answers
50
views
Number of 1-runs
A binary string is a word containing only $0$s and $1$s. In a binary string, a
1-run is a non-extendable substring containing only $1$s. Given a positive
integer n, let B(n) be the number of $1$-runs ...
2
votes
1
answer
114
views
How to prove a binary decomposition of $x(1-x)$?
Trying to find the variance of Brownian bridge (maybe not in the standard way) I settled on the formula:
$x(1-x) = \sum\limits_{k=1}^{+\infty}2^{k-1}\left(-\frac{b_k}{2^k}+\sum\limits_{i=k+1}^{+\infty}...
- 105
1
vote
0
answers
65
views
Direct conversion from base 2 to base 3 [duplicate]
Is there any way to convert a number that is represented in base 2 directly to base 3? Or do we need to always convert to base 10 first in order to get to base 3?
- 311
0
votes
0
answers
50
views
How do we add multiple binary bits with carry using boolean operators XOR and AND.
My question is similar to How do I add multiple binary numbers without using a partial sum?.
For example, if we add two bits, a and b, then sum bit = a XOR b and carry bit = a AND b.
Is there a way to ...
