Questions tagged [binary]
For questions about representing numbers in base 2 or performing arithmetic on them.
109
questions
0
votes
2answers
57 views
How come the set of all binary strings is uncountable?
Sorry for bumping this very old problem which already has answers on multiple SE sites, but I just cannot understand any of the answers.
Let $\Sigma_{bool} = \{0, 1\}$.
Then, $(\Sigma_{bool})^*$ is ...
0
votes
1answer
38 views
Changing binary counter structure such that increament and decreament methods will work in O(1) amortized
Just trying to solve the second part of a question with two parts.
First part was to prove that you can't add decrement method to a standart binary counter without hurting the amortized complexity and ...
0
votes
0answers
20 views
Computing with Extra States
So, computing largely operates through states of 0 or 1, this I am aware of. But I do have a question, is there a meaningful difference in computing using more states. For example, 0, 1, and 2. ...
0
votes
0answers
37 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 ...
1
vote
2answers
37 views
Half precision floating point question — smallest non-zero number
There's a floating point question that popped up and I'm confused about the solution. It states that
IEEE 754-2008 introduces half precision, which is a binary
floating-point representation that uses ...
1
vote
1answer
37 views
How to perform AND on binary “recursive repeating sequences”?
Suppose, we have a two binary sequences, encoded as "recursive repeating sequences" (I don't know exactly how to name them). Each sequence can contain other sequences and has number related ...
1
vote
2answers
33 views
Why are binary numbers sometimes written with one or more leading zeros that don't change the number (quantity) represented?
Binary numbers like '0110', or '00100101' are seen very often in all contexts. What are the leading (left hand side) zeroes for? Why did the writer not write '110' and '100101', respectively?
0
votes
1answer
27 views
while loop for bitwise conversion program
int counter(char c){
int count = 0;
while (c!=0){
if((c & 1) !=0)
count++;
c = c >> 1;
}
}
I am trying to understand a ...
1
vote
3answers
33 views
Negative Numbers in 32 bit Floating Point IEEE Numbers
So I understand the logic behind converting positive decimal numbers to IEEE 32 bit floating numbers but I'm not completely sure behind the negative one's. If for example we have a decimal number say -...
1
vote
1answer
73 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
40 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 ...
3
votes
4answers
73 views
Is there a binary representation where the encoding distance grows with the arithmetic distance?
I need to binarily encode/decode small integers (around 10 bits), in such a way that the hamming distance of the encoded number grows monotonically with the (absolute value) arithmetic distance of the ...
1
vote
1answer
74 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
1answer
50 views
Assign few binary variables to make all polynomials identically zero
I have 50 polynomials $f_i$ over binary variables $(x_1,\ldots,x_{100})$. Also $f_i(0,0,\ldots,0)=0$
for any $i \in [1,50]$. I want to assign few variables so that all $f_i$ will be
identically zero. ...
5
votes
2answers
119 views
How do computers *really* work? (at the most basic level)
While learning about computers I will read about RAM and Storage and the CPU, and while these explain the architecture of a computer and how parts of a computer work together, I still don't understand ...
1
vote
1answer
110 views
How can you represent a Huffman-tree in Hex?
I was trying to store a Huffman tree in a binary file recently. I thought it wouldn't be a big problem since you actually have the binary codes already in front of you.
Well, the difference is that ...
1
vote
1answer
25 views
Where does the decimal to binary “Divide by 2” algorithm come from?
I don't know if this board would be an appropriate place for this question, but I have been trying to figure out how the divide-by-2 decimal to binary conversion trick works: in which you divide the ...
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?
...
1
vote
1answer
17 views
2's complement substraction
I need to perform 2's complement operations on -50 - -48
From a mathematical point of view the following would be true.
-50 + 48 = -2
If I would follow the steps I would have:
I got to this result by ...
0
votes
1answer
30 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 ...
-2
votes
1answer
64 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 ...
3
votes
1answer
115 views
Greedy algorithm for subset sum on powers of 2
I have some $n$ numbers which are powers of $2$, say $a_1,a_2,a_3,\ldots,a_n$ which are not necessarily all distinct. I have option to give them any sign. I have to find if I can make their sum after ...
0
votes
1answer
42 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
38 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 ...
1
vote
2answers
43 views
Simple question about signed integer multiplication
If you have a signed integer int x = any
And then state that x < 0
Is the following statement true or false?
...
0
votes
1answer
40 views
Probability of loss using a binary symmetric channel
Today we talked about Information Theory and the binary symetric channel.
For newbies here is a little explanation :
For instance if I want to send a binary to someone :
The bit will be "flipped&...
1
vote
1answer
135 views
Converting Decimal Numbers between 0 and 1 to Binary
I've been playing around with a program I wrote that converts decimal numbers to binary numbers and i've noticed that eventually, after applying the algorithm (multiply by 2, subtract 1 if greater ...
1
vote
2answers
57 views
Is a file a string of zeros and ones?
Is a computer file just a string of zeroes and ones? If so, can it start with zeroes?
I have not been able to find an answer, surprisingly.
1
vote
1answer
18 views
Conversion of fractional part of a hexadecimal number to binary
The Number is given as : (C012.25)Hexadecimal
I have to convert it into octal .
So I converted it into Binary First and got the result as : 1100000000010010.01000000
(Since each bit in hexadecimal ...
1
vote
1answer
38 views
2d cellular automata Wolfram binary codes
This is a similar question to How 2d cellular automata rules works?
However, the answer there did not provide me what I am looking for. Specifically, I want to be able to render these 2d cellular ...
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]?...
1
vote
1answer
84 views
How does computer memory store the file name?
I have this doubt for long time. When i save a notepad file, it takes the memory for the information in the file. let's say, I type 'ABC' in notepad and saved the filename as stack, it shows that the ...
-1
votes
1answer
48 views
How does malware enter the computer and take control on a binary or machine code level?
Malware can enter a computer in various ways, but I would like to know how it is able to simply use 0's and 1's and machine code to take over a computer and how it can stay hidden from antivirus ...
0
votes
2answers
530 views
Binary subtraction with numbers in 2's complement
How can i perform binary subtraction of two numbers that are already in 2's complement?
I have to subtract 01010011 from 10100110,both numbers are in 2's complement.
I know that 10100110 is -90,and ...
2
votes
1answer
41 views
Does a megabyte represent (2^8)^1000000 bits in base2? Isn't that more than enough combinations to represent everything?
Every introductory CompSci resource I can find goes through how 8 bits are in a byte, etc. So a byte can store some 2^8 values in binary. Then when asking about four bytes, we can assume this is (2^8)^...
0
votes
0answers
38 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'...
1
vote
1answer
38 views
Where is the theory about “binary toggling games”?
Let us -- using parameters $M, N$ and $L$ --
create an ordered set of size $M$ of $N$-bit long vectors $V$ and initialize them randomly: $V_k[i] = b \sim Bin(n=1, p=0.5)\ \forall i \in
\{0\ ..\ N-1\}...
1
vote
1answer
104 views
Binary to ASCII using logical operations
I am learning Computer Architecture from Introduction to Computing Systems (2nd Edition) and am stuck on this question.
What operations can be used to convert the binary representation of 3 into ...
1
vote
1answer
25 views
binary representation of ip prefixes
How does an ip prefix
90.0.0.0/4
translate to
0101∗
in binary
and
10.0.0.0/2
to ...
2
votes
1answer
43 views
Sums of $2^{-l}$ that add to 1
Consider the following problem:
You are given a finite set of numbers $(l_k)_{k\in \{ 1, ..., n \}}$ such that $\sum_{k=1}^n2^{-l_k}<1$. Describe an algorithm to find a set $(l'_k)_{k\in \{ 1, .....
1
vote
1answer
148 views
Calculating direct sum of 2 binary numbers
If we have say,key=‘0110‘ and 𝑚=‘1100‘, how will 𝑚⊕key mod 2 be calculated and what will be the answer equal to?
0
votes
2answers
76 views
What needs led to the implementation of ASCII codes?
Prior to ASCII existing, we already had at least four number systems, namely
Binary
Decimal
Octal
Hexadecimal
So what were the needs that lead to the ...
0
votes
1answer
99 views
Number of nodes of given height in binary heap
Show that there are at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$ in any $n$-element binary heap.
How can I show this? Or, how can I prove this?
2
votes
3answers
133 views
Name of binary encoding scheme for integer numbers
I once found on Wikipedia a nice technique for encoding $k \in (2^{n-1}, 2^n)$ uniformly distributed integer numbers with less then $\log_2n$ average bits/symbol, thanks to a simple to compute ...
0
votes
3answers
701 views
Why the 127 encodings of ASCII needed to be extended to 256?
As you all know the ASCII chart needed to be extended from 127 encoding to 256, I can't really see why. Some google expert on Coursera said "We needed that because of the foreign languages".
I still ...
3
votes
3answers
226 views
What are some uses of the Thue-Morse sequence in computer science?
Note: I come from a mathematics background.
The Thue-Morse sequence $t_n$ is a binary sequence that takes the value $0$ at the positive integer $n$ if the number of $1$s in its binary expansion is ...
1
vote
0answers
34 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
1answer
39 views
Given a binary tree $t$, prove that $size(t) < 2^{h(t)}$
I was able to prove that $size(t) \leq 2^{h(t)} - 1$ for any binary tree $t$, however I wasn't able to do anything reasonable with this statement.
I know it's a proof by induction and that the ...
