Questions tagged [binary]

For questions about representing numbers in base 2 or performing arithmetic on them.

29 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
124 views

Partitioning through block moves to the end

Suppose we have a binary string $s$. We wish to partition this string in a series of $0$s followed by $1$s (alternatively: we wish to sort), using only one operation: moving three consecutive elements ...
2
votes
0answers
30 views

How can I optimise a 8b10b encoding for maximum alignment?

Imagine you encode an 8 bit symbol as a 10 bit symbol that is sent sequentially over a wire. The goal at the receiver is to detect the byte boundary. Since there are 4 times more encoded symbols than ...
2
votes
0answers
33 views

If 2's complement is the best way to represent numbers in computers, why worry about BCD and other binary codes?

I'm studying Digital Logic and Design. And in the first chapter, there's all this information about various binary codes. I did some searching on youtube and found this awesome video - https://www....
2
votes
0answers
178 views

K-ary tree that wrapped around

I'm not sure the best way to name this problem, but basically I need to construct a complete $k$-ary tree for $k \geq 2$ which has this nice property as $k=1$ tree that we can create a ring out of it. ...
2
votes
1answer
351 views

What exactly is a “binary file”?

I suspect this may be more of a concept / theory question, but, I haven't been able to wrap my brain around what exactly a binary file is. I've read links such as the below: https://en.wikipedia.org/...
1
vote
1answer
48 views

For two large (10^6) integers A and B, find the number of set bits in the result of their multiplication

I've recently stumbled upon a problem that I struggle realy hard with ever since. There are two large decimal integers, order of magnitude $10^6$. The task is to find how many bits in the binary ...
1
vote
0answers
39 views

Optimize binary multivariate polynomial multiplication

You have a few variables that can only assume the values 0 or 1 and you use those to form two polynomials. Is there a way to multiply the two polynomials that is faster than O(n²) where n is the ...
1
vote
0answers
11 views

About the paper Privacy-preserving in association rule mining using an improved discrete binary artificial bee colony

I don't understand two parts in this paper: The min notion on page 4 line 357 (equation 10d): I understand this as to find all the $M_{10}$, $M_{11}$, $M_{01}$ first and then try to minimize the ...
1
vote
1answer
72 views

Create binary numbers with a described pattern

I am looking for an algorithm that can create binary numbers following certain patterns. Let $n$ be the size; and assume that is a power of 2. Let $E$ be the exponent; $n = 2^E; k = \log n$. The $0, 1$...
1
vote
0answers
33 views

relationship between binary numbers and binomial heaps

I understand that a binomial heap can be represented as binary numbers according to the degree of each tree but what exactly is the relationship between inserting a new node into the binomial heap and ...
1
vote
0answers
379 views

Most efficient way to calculate log base 2

I recently started learning stuff with bits and now while I was solving one problem, I started thinking what is the most efficient way to calculate $$\lfloor \log_{2}K\rfloor$$ What I started ...
0
votes
0answers
13 views

How does the CPU take electrical signals from keyboard inputs and display numbers and letters on a computer screen?

Lets say the CPU receives an input of electrical signals from the user via keyboard and for this example, the electrical signals are off off off on PLUS off off on off. In binary, it would be ...
0
votes
0answers
35 views

Efficient method for finding 1's in binary representations

Say I have a binary number of N bits, and I need to find every combination that have M 1's. For example, if N = 3 and M = 1, then 100, 010, 001 are the allowed combinations. I have read that a more ...
0
votes
0answers
17 views

Binary 2's complement to decimal

I need to transform 2's complement from binary to decimal The binary integer is 10001001 This is my thought process. Could someone validate my thought process or correct it, please? ...
0
votes
1answer
26 views

How can I tell if a bit pattern can represent offset gray-code?

I have a very poor understanding of gray code in general and I find it to be a difficult thing to learn. While trying to learn about it I stumbled upon this seemingly looking trivial question that I ...
0
votes
1answer
40 views

is duality principle in boolean algebra is true for every expression

Let say A = 1 and B = 1 and then A+B = 1 now by using duality(replacing or gate by and gate and 1 by 0) we can say that, A.B = 0 but this is not 0, because 1.1 = 1, so please anyone clear my ...
0
votes
0answers
37 views

How did we go from Binary to something like Python?

If there's one thing the pandemic has shown us its that High school Geometry did not save us. I am a high school math teacher and I understand my job and its usefulness only exist in a post scarcity ...
0
votes
0answers
42 views

Is $x$ in the working range [3,2]?

Consider $x$ = $(0.1001)_b$ and $F$[3,2]. ($F$[3,2] is the set of all floating point numbers with 3 digits in the mantissa and 2 digits in the exponent.) The question is $x$ in the working range [3,2]?...
0
votes
0answers
37 views

CNF encoding of additions

I have $m$ equations of the following form: $$x_1+x_2+\cdots+x_n=s,$$ where each variable is either 1 or 0, and the total number of variables is $m\approx3{,}000$. So I’m thinking of modeling each ...
0
votes
1answer
46 views

XOR of three integers where each pair's XOR is the other integer

I have three positive integers, a, b, and c. I know that $a\oplus b\oplus c=0$, so I got that each pairwise xor has to be the other positive integer. $a\oplus b=c$, $b\oplus c=a$, and so on, but I can'...
0
votes
0answers
113 views

Binary to Decimal Algorithm Explanation

I came across some code today for converting binary to decimal, and I realised that I don't fully understand how it works. Here it is in Python: ...
0
votes
0answers
123 views

How does normalised floating point binary work with two's complement?

I'm doing AQA a-level computer science, and the specification for which states that: Exam questions on floating point numbers will use a format in which both the normalised mantissa and exponent are ...
0
votes
0answers
33 views

Converting a decimal to IEEE754 32-bit binary number

Convert 0.625 to IEEE754 32-bit binary number. 0.625 x 2 = 1.250 0.250 x 2 = 0.500 0.500 x 2 = 1.000 So, ...
0
votes
0answers
44 views

Find maximal matching in tree in $O\left(\frac{n}{\log n}\right)$

As any tree can be described as a binary sequence ($i$-th bit is 0 if the edge goes down and 1 otherwise, every edge is travelled twice $-$ up and down, so such sequence's length is $2 |V| - 2$), any ...
0
votes
0answers
110 views

Worst case lower bound of binary search

For the question below, it is asking to prove the lower bound on the worst case is log(n). I have no problem proving this and the solution makes 100% sense to me. However, there is a comment at the ...
0
votes
0answers
174 views

Is this the right way to convert a negative floating point number in binary using two's complement method?

I'm a cs student and i've just started learning about binary arithmetic.I have to do this homework assignement to get prepared for exams..I'm having some trouble figuring out how to convert a negative ...
0
votes
0answers
52 views

Avoiding overflow when comparing between 16-bit numbers

Let's say I have a 16-bit number system. and let $a, b$ a 16-bit numbers in this system. I know that the numbers I can represent in this system are between $−32,768$ and $32,767$. Let's say I want ...
0
votes
0answers
122 views

As a number (base 10) approaches infinity, what would be longer? Represented in BCD or Base-2?

My professor asked this question in his lecture class and I can't figure out the answer. My guess is BCD because you can't use up all the numbers (10 to 15), so you eat up space?
-2
votes
1answer
56 views

Consider 4 positive integers a,b,c,d having exactly 10^11 bits (considering the leading zeroes) in the binary representations

Consider 4 positive integers a,b,c,d having exactly 10^11 bits (considering the leading zeroes) in the binary representations. Positions are numbered from 1 to 10^11. Every 3rd bit of a is equal to 1 ...