Questions tagged [binary]

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

Filter by
Sorted by
Tagged with
-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)?
user avatar
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'...
user avatar
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 ...
user avatar
-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 ...
user avatar
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 ...
user avatar
-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 ...
user avatar
  • 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....
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
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 ...
user avatar
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 $...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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$. ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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: ...
user avatar
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, ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
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$ (...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 \...
user avatar
  • 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$...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 (...
user avatar
  • 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: ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 -- "...
user avatar
  • 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. ...
user avatar
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 $...
user avatar
  • 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 ...
user avatar
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}...
user avatar
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?
user avatar
  • 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 ...
user avatar

1
2 3 4 5
32