The binary tag has no wiki summary.
14
votes
8answers
911 views
Fractions in binary?
How would you write a fraction in binary numbers; for example, $1/4$, which is $.25$? I know how to write binary of whole numbers such as 6, being $110$, but how would one write fractions?
10
votes
1answer
299 views
The sum of powers of two and two's complement – is there a deeper meaning behind this?
Probably everyone has once come across the following "theorem" with corresponding "proof":
$$\sum_{n=0}^\infty 2^n = -1$$
Proof: $\sum_{n=0}^\infty q^n = 1/(1-q)$. Insert $q=2$ to get the result.
Of ...
9
votes
1answer
360 views
Finding Expressively Adequate truth Functions
I was wondering if someone could help me count the total number of Truth Functions of 3 variables, that can generate all the possible truth functions..
I got 56 but I'm not sure of the answer.
EDIT: ...
8
votes
2answers
61 views
Are the high-order bits of $n^2$ as likely to be zeroes as ones?
Let $B_i(n)$ be the $i$th bit in the binary expansion of $n$, so that $n=\sum B_i(n)2^i$. Now let $n$ be randomly and uniformly chosen from some large range, and let $E(j)$ be the expected value of ...
6
votes
2answers
392 views
It it possible to “compress” a list of large numbers using their prime factors?
On a computer I can have integers on arbitrary size thanks to GMP, so it's represented in base 2 in memory.
I'm wondering if it's possible in theory to use less memory if I store only prime factors ...
5
votes
10answers
553 views
Function that sends $1,2,3,4$ to $0,1,1,0$ respectively
I already got tired trying to think of a function $f:\{1,2,3,4\}\rightarrow \{0,1,1,0\}$ in other words:
$$f(1)=0\\f(2)=1\\f(3)=1\\f(4)=0$$
Don't suggest division in integers; it will not pass for ...
5
votes
2answers
113 views
Nim addition- binary addition without carrying
A nim addition table is essentially created by putting, in any cell, the smallest number not to the left of the cell and not above that cell in its column. However, I know for a fact that nim addition ...
5
votes
1answer
103 views
What function $f$ such that $a_1 \oplus\, \cdots\,\oplus a_n = 0$ implies $f(a_1) \oplus\, \cdots\,\oplus f(a_n) \neq 0$
For a certain algorithm, I need a function $f$ on integers such that
$a_1 \oplus a_2 \oplus \, \cdots\,\oplus a_n = 0 \implies f(a_1) \oplus f(a_2) \oplus \, \cdots\,\oplus f(a_n) \neq 0$
(where the ...
4
votes
2answers
171 views
Why does the $2$'s and $1$'s complement subtraction works?
The algorithm for $2$'s complement and $1$'s complement subtraction is tad simple:
$1.$ Find the $1$'s or $2$'s complement of the subtrahend.
$2.$ Add it with minuend.
$3.$ If there is ...
4
votes
1answer
152 views
How can I solve simple equations involving binary operators?
I have some simple equations like:
A = (X AND 1779038349) XOR ((X AND 3144134329) XOR 7047511487)
Where A is some constant and X is unknown (all numbers are 32 ...
4
votes
1answer
96 views
A question dealing with residual codes.
I've been reading about residual codes, and have come across several statements that I am having trouble showing.
(1.) By using the residual code, one can show that a $[16, 5, 8]$ binary code ...
4
votes
1answer
67 views
Proving that $A_2(13,7) = 8$
It is not too difficult to find a binary code consisting of $8$ words, each $13$ bits long, keeping the distance between every pair of words at least $7$. I know it is not possible to find $9$ words ...
3
votes
4answers
69 views
Simple binary subtraction
$$101110 - 110111$$
Did the 2's complment and cannot get to the answer. The answer is apparently
$$-1001$$
I did 2's complment on the $$110111$$
and performed addition but did not get to the ...
3
votes
3answers
669 views
A proof that powers of two cannot be expressed as the sum of multiple consecutive positive integers that uses binary representations?
In this earlier question, the OP asks for a proof of the statement
Every natural number not of the form $2^k$ for some atural number k can be written as the sum of two or more consecutive positive ...
3
votes
2answers
86 views
Binary Sequence Block
More of an informatics question, rather than applied mathematics -
Source - Zonal Informatics Olympiad 2011 Question Paper
Although, I've tried a few brute methods, I haven't really understood ...
3
votes
1answer
828 views
How many bits needed to store a number
How many bits needed to store a number $55^{2002}$ ?
My answer is $2002\;\log_2(55)$, is it correct?
3
votes
2answers
41 views
Recognize a valid binary Golay codeword
Are there any properties of a binary [24,12,8] Golay code which would allow me to say, for example, that a given 24-bit word is or is not a Golay codeword for some generator matrix? That is to say, is ...
3
votes
1answer
52 views
q-ary code/Latin squares
For any value of $q$ the largest number of elements in any q-ary code $C$ of length $4$, distance $3$ is $q^2$. How can we prove that this is attainable iff there are a pair of mutually orthogonal ...
3
votes
1answer
60 views
Find the solutions of Boolean equations
It's given 4 Boolean equations. I need to find the number of solutions of each.
$a)\ x_{1}x_{2}\oplus x_{2}x_{3}\oplus\ ...\ \oplus\ x_{n-1}x_{n}=1$
$b)\ x_{1}x_{2}\vee x_{2}x_{3}\vee\ ...\ \vee\ ...
3
votes
1answer
303 views
Fun ideas for project on Encoding
My university is organizing a project for college students (age around 17) around the subject of encoding (not encypting! See also http://danielmiessler.com/study/encoding_vs_encryption/). As a ...
3
votes
0answers
148 views
An Upper Bound for an $[n,k,d]$ Linear Binary Code.
I've been reading about the various upper bounds for different types of codes. Recently, I came across a statement that is similar to the Singleton Upper Bound that I am having trouble proving. The ...
3
votes
1answer
506 views
Binary representation of powers of 3
We write a power of 3 in bits in binary representation as follows.
For example $3=(11)$, $3^2=(1001)$ which means that we let the $k$-th bit from the right be $1$ if the binary representation of this ...
2
votes
2answers
190 views
Count the number of n-bit strings with an even number of zeros.
I am currently self-studying introductory combinatorics by reading Introduction to combinatorial mathematics. I am currently in the first chapter, and I have a question regarding one of the examples. ...
2
votes
2answers
57 views
Twos complement notation question?
I have a quick question how do you do the two complement system,
For example say I have in two complement a $6$ which is $0110$ and $3$ which is $0011$ and I want to add
$6+(-3)$ I know what five is ...
2
votes
3answers
191 views
Representing a binary number
Suppose you wanted to write the number 100000. If you type it in ASCII, this would take 6 characters (which is 6 bytes). However, if you represent it as unsigned binary, you can write it out using ...
2
votes
2answers
64 views
Expected number of 1s for a random integer
For an integer $K$ randomly chosen from $0,1,...,N$. What is the expected number of ones in $K$'s binary representation?
A special case of the problem is when $N=2^k - 1$, in which the expected ...
2
votes
1answer
57 views
Is there a sequence of primes whose decimal representations are initial segments of each other?
I.e., is there a sequence of primes whose decimal expansions have the following form:
$$a_1,\ a_1a_2,\ a_1a_2a_3,\ a_1a_2a_3a_4, \dots$$
What about with the order of the digits reversed, so each ...
2
votes
3answers
342 views
Terminating decimal number which is not terminating in binary
I know that when converting a decimal number from base 10 to base 2, the result might be not terminating, even though the number is terminating in base 10.
For instance, 0.2 -> 0.0011 0011 0011 ...
...
2
votes
2answers
108 views
multiple xor (sum of parities)
If we have:
$b_1 \oplus b_2 = b_1 (1 - b_2) + b_2 (1 - b_1)$
what is (or are, if there are different versions) the compact general formula for a multiple "summation":
$b_1 \oplus b_2 \oplus \dotsb ...
2
votes
1answer
64 views
Binary notation in Magma
As a part of programming an Elliptic Curve Method with montgomery coordinates in Magma, I need to have an algorithm to convert a number from decimal notation to binary notation. Since there is no ...
2
votes
4answers
993 views
binary representation of a real number
In Baby Rudin,I find reference to the fact that the binary representation of a real number implies the uncountablity of the set of real numbers.(page 30)But I have two questions:
Does every real ...
2
votes
1answer
54 views
Factoring of exponents in Simon's algorithm
In derivations of Simon's algorithm (e.g., p. 4), it's often meant to be apparent that
$$(x_0\oplus s)\cdot y=(x_0\cdot y)+(s\cdot y)$$
where $\oplus$ is "direct sum modulo 2", $x_0,s,y$ are all ...
2
votes
1answer
79 views
Random infinite binary sequence
What I mean by random infinite binary sequence is an infinite sequence of $0$'s and $1$'s with probability of occurrence in this sequence equal to $1/2$ (all digits being equally likely).
How is it ...
2
votes
1answer
84 views
Proof about infinite sum
Define recursively-defined function $f_x:N\to\{{0,1\}}^N$ where x belongs to [0,1):
For $n=1$,$f_x(1)=0$ if $x$ belongs to $[0,1/2)$, $a_1=0$, $b_1=1/2$ in this case;
$f_x(1)=1$ if $x$ belongs to ...
2
votes
1answer
208 views
Calculating CRC code
I think I may be under a misconception. When calculating the CRC code, how many bits do you append to the original message? Is it the degree of the generator polynomial (e.g. x^3+1 you append three ...
2
votes
1answer
51 views
Partitions of binary numbers into binary numbers with fixed digits?
If we are to have (two, for example) binary numbers, such that their sum is $100111010_2$, and given that the first number has 5 ones, and the second number has 3 ones, can I find the numbers that ...
2
votes
1answer
103 views
Subset of bits of factors of integer
Is there any information on the internet concerning analysis of subsets of bits of the (unknown) factors of any given integer n? Me being unskilled with phrasing things properly for google has given ...
2
votes
0answers
21 views
Fast fourier transforms of random binary data
I am a physicist who is trying to make sense of FFTs and binary data.
Say I have a series of random binary data, which is measured with a repetition rate of 400Hz (interval time of 0.0025s). I have a ...
2
votes
0answers
81 views
Finding the binary representation of the $n$th Fibonacci term
Objective: To find the binary representation ( or no. of 1's in binary representation) of nth term in Fibonacci sequence where n is of the order 10^6.
My current approach: Find nth term (in decimal) ...
2
votes
1answer
109 views
Floating point binary arithmetic question
I'm doing a basic class on computer architecture and we dwell into Floating Point Arithmetic, I'm not looking for someone to solve my homework, I'm actually just going through old exams and I'm kinda ...
1
vote
1answer
95 views
Arrangement of binary bits
I have $n$ numbers of bits. $\frac{n}{2}$ of those bits must be $1$ and $\frac{n}{2}$ of those bits must be $0$ (meaning $00001111$ or $10101001$). How many different binary numbers can I make?
Is ...
1
vote
2answers
139 views
What are the last four digits in the binary expansion $1234^{5555} + 4321^{5555}$?
I'm having a lot of trouble figuring out this discrete math question:
What are the last four bits in the binary expansion of 1234^5555 + 4321 ^5555?
I need to ...
1
vote
3answers
150 views
Way of simplifying binary multiplication
Is there a way to simplify multiplication of binary numbers regardless of digits? Or do we always have to resort to 10-base multiplication? As computers do multiplication, there should be ways to ...
1
vote
2answers
189 views
Where does binary arithmetic/manipulation enter the mathematics/engineering curriculum?
Binary arithmetic is both an educational basis for elementary logic and an pervasive tool for practical mechanics in managing computer systems (at a very particular level). That is the state of ...
1
vote
3answers
54 views
Binary Division
IF I convert the dividend and divisor into decimal, perform the division and convert the remainder and quotient back in to binary will I get correct answer?
I'm doing this:
$630 ÷ 13$
Quotient=$48= ...
1
vote
1answer
35 views
Multiples of $5$ in base $2$
As a follow-up question, what can be said about multiples of $5$ in base 2?
I think I must look at the last two digits, but I am not sure what the whole idea might be.
1
vote
1answer
25 views
XOR for 10 and 20
I know that this is the XOR truth table.
A B Q
------
0 0 0
0 1 1
1 0 1
1 1 0
I have a = 10; and b=20; Their respective binaries are a=1010; and b=10100;
a ...
1
vote
1answer
65 views
XOR of Binary Numbers to Reach a Given Number
Given a set
S = { s1, s2, s3, ... sn}
of Binary Numbers , I need to find if a given Binary Number X with only 1 bit position set as 1 (..00001000...), can be ...
1
vote
1answer
56 views
Even numbers in base 2
We all know even numbers are the ones that end in even digits. How do we analyze even numbers in base 2?
1
vote
1answer
143 views
How do you work with the IEEE 754 32-bit floating point format?
I'm having trouble completing a question that deals with the IEEE 754 32-bit floating point format, primarily because I don't know how to use it. I was hoping someone here could clarify for me using ...
