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

learn more… | top users | synonyms

0
votes
1answer
153 views

Complement Calculations - Why do I get different answers with ones' and twos' complement?

I am finishing an assignment related to complement calculations. The question is as follows: ...
0
votes
1answer
622 views

Add Hexadecimal that is in 2's complement.

Perform the following additions. The corresponding 16-bit binary numbers are in 2's complement notation. Provide your answers in hexadecimal. I'm not sure about this one, am I doing the 2's ...
4
votes
1answer
48 views

How many bits in position i are turned on in a list of values 0-N?

Is there an equation that reflects how many values have a bit in position $i$ turned on for a list of values $0-N$?. For example if $N=5$, our numbers are represented in binary as: 000, 001, 010, ...
0
votes
0answers
39 views

Probability, linear independence and study of variant of Lights Out

Using Arduino, some leds and pushbuttons I've created a simple variant of the mathematically popular game "Lights Out". In my variant, the starting configuration is always all lights on; what changes ...
0
votes
1answer
64 views

What is the significance of the last two digits of a 2's complement number being 00?

What is the significance of the last two digits of a 2's complement number being 00? The first part of this question is what is the significance of the last digit being 0? I said that the digit ...
0
votes
1answer
396 views

Write the 6-bit 2's compliment representation of -32.

Write the 6-bit 2's compliment representation of -32. I think the answer is supposed to be something like "overflow" or some error. Because 32 in binary would be 10 0000, right? And -32 would be ...
1
vote
1answer
221 views

Range two's complement

The most used formula's to calculate the range of numbers in a two's complement system are + $2^{n-1}-1$ for the highest number and $-2^{n-1}$ for the lowest number. The problem is that this only ...
1
vote
1answer
80 views

Signed binary arithmetic

I'm having trouble with a fairly simply concept, signed binary arithmetic. I know how to do 1's and 2's complement, convert from binary, decimal, octal, and hex, multiply and add bytes and bits, but ...
1
vote
1answer
33 views

Question on irreducible polynomials and primes.

Consider the polynomial $p(x) = 1+\sum_{i=1}^d a_i x^i$ where $a_i$ is binary and not all $a_i$ are $0$. Is it possible that $p(2^n)$ is prime for all integer $n>-1 ?$
3
votes
1answer
66 views

How to take one's complement of a positive integer?

Of course we can do that by converting the number to binary and then converting it back to decimal, but to do that directly in decimal?
0
votes
2answers
54 views

Number of ones to the left of every zero in binary representation

I am seeking the computationally fastest way to determine the total number of ones to the left of every zero in the binary representation of a number. That is: for every zero, count the number of ...
4
votes
3answers
230 views

Number of binary strings with $n$ ones and $m$ zeros

$f(n,m)$ is the number of binary strings with up to $n$ ones and up to $m$ zeros. Prove that the number of possible strings is: $${n+m+2 \choose n+1} -1$$ I got to the point that: $$\sum_{a=0}^n ...
0
votes
1answer
408 views

How to calculate no. of binary strings containg substring “00”? [duplicate]

I need to calculate no of possible substrings containing "00" as a substring. I know the length of the binary string. Eg: for a string of length 4, possible substrings are: 0000 0001 0010 0011 0100 ...
1
vote
2answers
386 views

Why should we append zeros during CRC calculation?

Say we have M as message bits , why do we need to append r-zeros to M message bits before performing the division to obtain r-bit checksum. Why don't we directly perform the division on the M message ...
1
vote
0answers
193 views

Recurrent relation for number of ways to get a balanced n-binary tree

In answering a question related to binary trees, I came up with the following recurrent relation: Base cases: $$ f \left (1 \right ) = 1 $$ $$ f \left (2 \right ) = 2 $$ Recurrent relations: $$ f(n) ...
0
votes
4answers
2k views

How many 32 digit binary number combinations are possible?

How many 32 digit binary number combinations are possible? For example: $$00000000-00000000-00000000-00000000$$ $$00000000-00000000-00000000-00000001$$ $$00000000-00000000-00000000-00000010$$ $$.$$ ...
1
vote
2answers
144 views

Binary to Decimal

Is it possible to convert a binary pattern to decimal pattern consists of 0's and 1's without loop (iterations). Suppose if I have. ...
7
votes
1answer
109 views

Matrix + combinatorial or conditional probability: bit patterns

I'm trying to get my head around a problem, and it's not working. The problem: consider an NxN matrix that represents a binary number. For instance, a 4x4 matrix is a 16 bit number, a 6x6 matrix is ...
1
vote
1answer
153 views

Find the largest divisor of an integer $b$.

I want to find out an efficient method to calculate the largest divisor of a very big integer $b$ which can be up to $\large 2^{1000}$. That is, I want to find out an integer $a < b$, such that ...
0
votes
1answer
34 views

Relation on $n$-digit binary strings…

Let $X$ be the set of all $7$-digit bit strings 0100011, and let two elements in $X$ be related if the first and last bit matches. How many equivalence classes are there? Further, how many ...
2
votes
1answer
98 views

number of binary sets - combinatorics

Just ran into this question: let $f(n,m)$ be the number of binary strings where there are at most $n$ 1's and at most $m$ 0's. the empty string also counts as a string. show that ...
0
votes
1answer
125 views

Simplifying the Boolean binary equation

A'B + A'B'C + ABC'C' + AB' + AB'C' I need to simplify this boolean equation in simplest form but im not sure of my answer.
1
vote
2answers
914 views

Maximum run of zeros in a $n$-bit binary string

I came to know that, in a random string, one expects the longest sequence of zeros to be roughly of length $\log n$. I want to be able to prove this. For this I need to know the probability that the ...
4
votes
3answers
251 views

An odd question about induction.

Given $n$ $0$'s and $n$ $1$'s distributed in any manner whatsoever around a circle, show, using induction on $n$, that it is possible to start at some number and proceed clockwise around the circle to ...
1
vote
1answer
312 views

Quick question about binary strings

Determine the unambigious expression which generates every string in this set. The set of all binary strings which contains 001111 as a substring. I am thinking that the answer should be ...
3
votes
2answers
76 views

How do we know $p/q$ can be expressed as a terminating fraction in base $B$ only if prime factors of $q$ are prime factors of $B$?

On cs.stackexchange I asked a math question: How to demonstrate only 4 numbers between two integers are multiples of .01 and also writable as binary. Yuval Filmus answered with a explanation ...
6
votes
2answers
308 views

Complement of all-one vector in binary vector space

Let $V$ be a k-dimensional subspace of $(\mathbb{F}_2)^n$, such that vector $\vec{j}=(1,1,...,1) \in V$. Standard linear algebra shows that it is possible to find a $(k-1)$-dimensional space $W$ such ...
1
vote
1answer
155 views

Using partial fractions to find explicit formulae for coefficients?

The set of binary string whose integer representations are multiples of 3 have the generating function $$\Phi_S(x)={1-x-x^2 \over 1-x-2x^2}$$ Let $a_n=[x^n]\Phi_s(x)$ represent the number of strings ...
2
votes
1answer
168 views

Recursive equation for palindromes

Can someone help me determine the recursive equation for all binary strings that are palindromes? A binary string is a palindrome if it reads the same forward and backward. Examples of palindromes are ...
1
vote
3answers
95 views

Find the generating function for this set of strings

Let $a(n)$ be the number of $\{0,1\}$-strings of length $n$ which contain no $4$ consecutive $1$'s and no $4$ consecutive $0$'s (don't contain "$0000$" or "$1111$"). Find the generating function for ...
2
votes
0answers
174 views

Unambiguous expression for binary strings containing some substring

Is there some systematic way for finding an unambiguous expression for a binary string which contains a certain substring? For finding expressions not containing a substring, it is sometimes easy to ...
1
vote
0answers
142 views

Finding the maximum XOR metric

I'm trying to find a way to find n keys (x bits) where the XOR distance metric between them would be greatest. By XOR distance metric I just mean the value when two keys are XORed together. So for ...
0
votes
2answers
139 views

Binary Strings Question

prove that the following expression for a set of binary strings S is ambigious S = {101,1101,1011}* Thanks for all your help!
1
vote
1answer
187 views

Solving a constrained Lagrangian dual problem

Consider the following $\max-\min$ integer programming formulation expressed in the binary decision variable $\mathbf{z}$: $$\begin{align*} \max&m \\ s.t.&\\ m \leq& s_i + \sum_j^J ...
5
votes
2answers
370 views

Random binary matrix with given rows and columns sums

I need to generate a random binary matrix $(n, n)$ whose rows sums and columns sums are $4$. I don't manage to find a quite efficient algorithm to do this. Have you an idea please ? NB : The ...
0
votes
2answers
249 views

Closed formula to count number of binary numbers of length $x$ having at least $y$ $1$ bits

I'm interested in solving a sub problem of the algorithm related question from SO How many binary numbers having given constraints .... The sub problem being, having $x \geq y$ determine how many ...
0
votes
2answers
105 views

Why is $ab + bc + c\bar{a} = ab + c\bar{a}$ true in binary?

I was simplifying the equation of a logic gates problem and I realized that ab + bc + cā and ab + cā followed the same truth ...
1
vote
2answers
63 views

Special binary string

Imagine a binary string of increasing length, up to infinity. What makes it so special? Well, just a simple "rule": for any given length (odd or even), if one folds the string in half, there is at ...
0
votes
0answers
31 views

Transformation of binary data

I have a function that I try to optimize using Particle Swarm Optimization. Objective function gets a binary string. So these binary strings are candidate solutions of the subject function. I can ...
0
votes
1answer
432 views

Left shift and right shift calculation ..

i need to calculate left and right shift in java. in java i am able to code this. but i like to know how it calculate . Can any body here enplane me with Example. I am using below logic, plz check ...
1
vote
1answer
78 views

Minimizing deviations from threshold value from a given group of numbers

Given a set of numbers $a_n$, a threshold level $t$, how do I find the combination of numbers that will sum to at least the threshold with minimum deviation? Added: That is, they must always exceed ...
1
vote
2answers
86 views

Decimal Floating Point to Shortest Binary

Might be more of a Comp Sci question so apologies if it's not appropriate. Basically I have a range bounded by two floating-point decimals <1. I need to find a short binary number lying between ...
8
votes
2answers
79 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 ...
1
vote
0answers
33 views

Predict binary occupancy vector from history of vectors

I have a set of binary vectors where each vector represents one day of occupancy in a house and consists of 48 elements (each element for 30 minutes of the day). Each element can be 1 meaning that ...
1
vote
1answer
226 views

What is the average Levenshtein distance between two random binary strings of length $L$?

For example, for length $L=7$, two random binary strings might be: 0100101 1010011 The Levenshtein distance here would be 5, as it would require 5 bit-flips to ...
0
votes
1answer
344 views

How are binary operations used in the real world?

Not necessarily a mathematical question, but how could binary operations be used in the real world? What applies to it?
1
vote
3answers
146 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
votes
1answer
602 views

Semigroups, monoids, & groups!

I need help determining if these are semigroups, monoids, or groups? a) $\mathbb Z ^+$, where $\#$ is defined as ordinary multiplication b) $\mathbb Z ^+$, where $a \# b$ is defined as $\gcd(a,b)$ ...
0
votes
2answers
315 views

Constructing a tree from an algebraic equation

How do I take an algebraic expression and construct a tree out of it? Sample equation: ((2 + x) - (x * 3)) - ((x - 2) * (3 + y)) If somebody can teach me in steps, that would be really helpful!
0
votes
2answers
260 views

Quick logarithm calculation

In coming up with an algorithm for finding log (10) base 2, these are my thoughts. I wanted to know if this makes sense and how could I truly make it more efficient. The requirements are strictly not ...