Questions tagged [binary]
For questions about representing numbers in base 2 or performing arithmetic on them.
133
questions
0
votes
1
answer
43
views
Difference between two's complement and sign-and-magnitude
I'm just starting to learn about representing numbers in sign-and-magnitude and two's complement, and both as signed binary integers two's complement if representing a negative number I should invert ...
1
vote
1
answer
19
views
Decomposing large bit mult or exp into smaller bit operations
Imagine a machine that can only hold N-bit values (N-bit uint).
The machine can also calculate the 2N-bit result of two operations: mult, exp.
The 2N-bit result is stored across 2 N-bit values (high/...
- 11
2
votes
1
answer
58
views
Cost of increasing a binary counter with a starting value n times
Consider a k-bit binary counter and suppose that in the beginning the value of the i-th most significant bit is $b_i$ for each $i = 0, . . . , k − 1$. Let $b = b_0 + 2b_1 +· · · + 2^{k−1}
b_{k−1}$. ...
- 369
0
votes
0
answers
19
views
Decimal Fraction to 6-digit binary
I'm new to the binary numbers, but I understand the general idea. I know how to convert signed integers to sign-and-magnitude, 1's complement and 2's complement of 6 digits. But what I find difficult ...
- 1
1
vote
1
answer
151
views
How do I find the regular expression for- All binary numbers greater than 110011
I am trying to solve a problem set to practice for an exam. How can I approach questions like these ? Is there a way to verify solutions or is it just trial and error ?
- 111
1
vote
2
answers
54
views
when is 2's complement used, or called into use in hardware
so when doing digital design, lets say building a calculator we only take the 2s complement of a negative number.
13+(-12)=1
001101 + 110100 = (1)000001
the 1 in parenthesis is overflow that "...
- 11
0
votes
0
answers
23
views
how would i go about creating a base 10 to base 2 converter
I am trying to create a calculator in excel for use in Minecraft later and I was wondering if the was any way to create and how I would create a base 10 to base 2 converter with only logic gates. if ...
1
vote
0
answers
22
views
Standard for representing a float scaled to a particular range?
TL;DR Is there a "standard" way to represent a float scaled to a particular range, such that we get maximum precision for the given bit depth, within that range?
I'll start with my general ...
- 111
0
votes
0
answers
140
views
8-bit binary to bcd converter Verilog
We have been given task to write a 8-bit binary to bcd converter Verilog code, using structural code NOT behavioural, is it possible to guide us how can we create 8-bit binary to bcd converter using ...
0
votes
1
answer
46
views
How do I determine the time and space complexity of the following algorithm?
I need to compute the time and space complexity in Big O notation for this algorithm I constructed for binary multiplication.
...
0
votes
0
answers
37
views
temporal compression of binary data
I have a sequence of source files that are very similar (akin to frames in a video), and each file can be compressed by a codec independently, but there is no temporal compression.
I want to further ...
- 101
0
votes
2
answers
34
views
Can you compare large numbers this way?
If you created two very large numbers represented by binary data (perhaps using sha512 with random input for each hash) could you determine what binary block is numerically larger by iterating over ...
- 103
1
vote
0
answers
46
views
From binary to unary and EXPTIME
I read in [Razborov, "An equivalence between...", p.248] that
It is well recognized in Theoretical Computer Science that when we change the representation of integers from binary to unary, ...
- 11
1
vote
1
answer
101
views
Prove every number in double precision 32-bit floating-point format can be represented in 64-bit format
Theorem: Prove every number in double precision 32-bit floating-point format can be represented in double precision 64-bit floating point-format.
64-bit format:
Attempt: Let $ b = b_0 ,...,b_{31} $ ...
- 223
0
votes
0
answers
18
views
How do parity file works. And can it retrieve all n bytes corrupted to a limit of M bytes segmet chunk?
I want to know if a parity file can correct all N bytes of segments present in a M byte file. It does it partially or completely.
For example:
I have a file of 5 MB and it have 8 bytes (8×8=64 bits) ...
- 35
1
vote
1
answer
59
views
How is Gene sequence files i.e FASTA files so compressible?
Why are Gene squencing file i.e FASTA files so compressible. It was stated on a site that few compression algorithms are capable of compressing these files to Gigabytes (from Terabytes).
And is it ...
- 35
0
votes
1
answer
27
views
What are the chances of hash collision given large input and small hash?
I have an input of 128 bits (binary, 0s and 1s) and want to hash this input with 32 bit CRC. But I am not sure if collision rate is moderate or too high ?
Is it 2^128/2^32 = 2^98.
And does that ...
- 35
0
votes
2
answers
109
views
Can more compression be achieved when data is sorted (in ascending or descending order)?
Let's say I have a file which is exactly 1 MB in size.
Contents of file are :
0001001000... upto 128 bytes (128 bytes per line in file).
If I sort it in ascending or descending order (using notepad+...
- 35
0
votes
4
answers
110
views
Why does the BOM consist of two bytes instead of one for example in encoding utf-16
Why does the BOM consist of two bytes instead of one for example in encoding utf-16?
Information about the order of bytes can be easily saved on just one byte.
Is it because it would be good for the ...
- 11
0
votes
1
answer
28
views
Can possiblity of hash collision be "zero" when we hash same file in different formats?
Let's say I have a file A, which is any normal file (pdf, jpeg, mp3 etc.)
Now I get the binary dump of file, say another file B{A}.
And the hexdump of file say, file H{A}.
Now I hash all the three ...
- 35
0
votes
1
answer
33
views
Which is faster "Sorting strings in ascending order" or "Counting the frequency of all strings "?
I have a binary file with lots of 128 bit strings:
For Example Line 1. 1000101001000100001111001010.....
Line 2. 011010010101001001010..... and many more.
I want to sort them in ascending order, and ...
- 35
0
votes
0
answers
15
views
What would be the simplest and quickest way to convert Morse code to "strict" binary?
I'm trying to find a way to easily convert strings of morse code into strings of "strict" binary, in the way that it is described in this answer. Specifically, where:
A dot is represented ...
- 1
0
votes
1
answer
82
views
How to represent $x$ in hexadecimal form where $x=2^n$?
When a value $x$ is a power of $2$, that is, $x = 2^n$ for some nonnegative integer
n, we can readily write $x$ in hexadecimal form by remembering that the binary
representation of $x$ is simply $1$ ...
- 149
1
vote
0
answers
58
views
Is it possible to find length of sum of two binary numbers without calculating sum?
I'm doing an assignment where I need to multiply two 16 bit numbers and store result as an 16 bit integer array.
a is binary with length of ...
- 11
1
vote
2
answers
58
views
Why is the time complexity of the Bit Manipulation solution to Binary Addition O(M + N)?
I am trying to understand why the time complexity of the Bit Manipulation solution (https://leetcode.com/problems/add-binary/solution/) to the Binary Addition problem is O(M + N), where M and N are ...
- 125
3
votes
1
answer
70
views
What is the nature of the two bits of data held in a computer memory cell?
I hope this question doesn't offend anyone. I start off by saying that I have and always had difficulty understand the language used in computer science so I have to interpret everything into the ...
- 33
0
votes
2
answers
275
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 ...
- 127
0
votes
1
answer
99
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 ...
- 49
0
votes
0
answers
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
1
vote
2
answers
246
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 ...
- 13
1
vote
1
answer
42
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 ...
- 71
1
vote
2
answers
69
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
1
answer
286
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 ...
- 167
1
vote
3
answers
517
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 -...
- 13
2
votes
1
answer
578
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 ...
- 21
1
vote
0
answers
58
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 ...
- 111
1
vote
0
answers
13
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 ...
- 11
3
votes
4
answers
108
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 ...
- 33
1
vote
1
answer
100
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$...
- 11
1
vote
1
answer
62
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. ...
- 33
5
votes
2
answers
267
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 ...
- 53
1
vote
1
answer
257
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 ...
- 13
1
vote
1
answer
61
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 ...
- 113
1
vote
1
answer
37
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 ...
- 13
0
votes
1
answer
47
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 ...
- 131
-2
votes
1
answer
71
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
1
answer
227
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
2
answers
70
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
0
answers
39
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
2
answers
59
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?
...
- 11