# Tagged Questions

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

27 views

### is the Root of a binary Tree counted as a node

I am working on this Homework questions and there's one thing I can't seem to understand. We are trying to proof using structural induction that some elements in T hold for the following statement :...
30 views

### Converting from Binary to Decimal help?

Can anyone help me solve this? Converting to decimal from binary that is signed...so also using twos-compliment. ...
20 views

Problem Consider the general chip-and-be-conquered recurrence relation: $T(n) = b_1T(n - 1) + b_2T(n - 2) + ... + b_kT(n - k) + f(n)$; for $n >= k$ for some constant $k >= 2$. The ...
45 views

### How would one go about solving these types of problems?

I'm totally lost. All I know is it has to do with binary trees and may need to be solved using induction. Show that every 2-tree with $n$ internal nodes has $n + 1$ external nodes. Show that the ...
63 views

### What was the original purpose for the binary system?

Obviously computers weren't around when binary was first created... was there a particular use for binary back then or was it just developed as another number system?
55 views

### Is this sum of Binary Numbers an Overflow?

I have a question of the likes of 21 + 11 I converted each number to binary getting: 010101 + 001011 I got a result of : $100000$ which is $32$ in decimal Thus it is correct that $21+11 = 32$. ...
40 views

### Decimal - Binary

Let N = 1 000 … 000 1 (n zeros), and M = 111 … 1110 (n ones). What is the decimal value of M and N assuming: a) Unsigned Binary Representation b) Two's compliment Representation c) Signed/Magnitude ...
25 views

### How many binary numbers can be represented with X number of number places?

How do we find out that in the binary number system, how many different numbers can be represented with a certain number of number-places? For example, suppose we have 8 number places, i.e. a 1's ...
50 views

### Binary expansion and bijection

Using the idea of binary expansion ($1011$ is $1\cdot2^0 + 1\cdot2^1+0\cdot2^2+1\cdot2^3 = 11$) to find a bijection that (a) maps $\mathbb{N}$ to the set of all finite subsets of $\mathbb{N}$ (b) ...
54 views

### Decoding BCH codes with permuted parity-check matrix

A normal t-error correcting $BCH(n,k)$ code over $GF(2^m)$ would be constructed using a generator polynomial g(x), which is the LCM of the minimal polynomials of $a,a^2,..a^{2t}$, with $a$ being a ...
30 views

### Operations on binary numbers, that have equal numbers of two available digits, that preserve this property?

I'm looking for operations on binary numbers that have the same number of the available digits, $0$ and $1$, such as $100011$, $100101$ and $10$. These could be integers as the examples given are, or ...
52 views

### Expected number of evaluated nodes

I have an array of zeroes with a length of $1024$. Suppose $n$ random elements are changed to $1$, the array now has $(1024-n)$ zeroes and $n$ ones. I want to find the position of all $n$ elements ...
119 views

### Switch flipping sequence with no repeats

Okay, you have N switches. They are all off. You may flip one switch at a time. You must visit each possible state of switches being flipped without repeating any state. At the end, you must be ...
96 views

### Find a recursive definition for inorder: binary Tree(T) → list(T ) where inorder(T ) is the list of nodes from an inorder traversal of T .

Find a recursive definition for inorder: binary Tree(T) → list(T ) where inorder(T ) is the list of nodes from an inorder traversal of T . I have no idea what this question is even asking me. What ...
176 views

### Converting a negative decimal with fractions to binary and hex

I am asking the question even though it has been answered before because I am looking at 3 different pages with 3 different answers right now. I am wondering how to convert a negative decimal with a ...
256 views

### orthogonal binary sequences

How to show that two binary sequences are orthogonal? For an example verify whether [0110001] and [0011101] are orthogonal
134 views

### Combinatorics - Counting the number of binary strings with specified length and sum, with substring constraints

Suppose I have a string of bits of length R. The sum of the bits must be equal to S, so there are S ones and R-S zeros. The longest string of ones cannot exceed X in length. Also the number of places ...
81 views

133 views

### Probability that two numbers differ by one bit

Assuming that t is the bit length of the numbers and that we can pick 2 random numbers (the same number cannot be chosen twice), which is the probability that the two numbers will differ by exactly ...
950 views

### Why are sums of powers of 2 able to give all numbers?

It is known that If we sum up a combination of numbers that are positive powers of 2(starting from 0 to infinity), we can get any number possible. (Correct me if this is wrong). Can anyone ...
107 views

### Why is 2's complement called this way?

So, I'm preparing for a test and one of the preparation questions is as follows: I can tell easily that 'a' and 'e' are just wrong and therefore these answers are irrelevant, but taking a look at ...
56 views

### How many bits to represent this integer?

If $$x = \left(\frac{n+1}{4}\right)^{(n+1)/2},$$ then how many bits do we need to represent $x$ in binary?
62 views

### Binary Integer Programming

I need to form teams. There are 8 projects and 60 students. Each project has different requirements. For example, out of 5 total requirements, project 1 has 2 requirements: must have a programmer and ...
292 views

### Why does the division algorithm work for converting between number bases?

I know and have observed that the the division algorithm can be used to convert any number in the decimal system to the binary system. However, I have tried searching for an intuition of why this ...
47 views

### Decompose negative power of ten in finite series

Suppose we have numbers $10^{-1}, 10^{-2}, 10^{-3}, ..., 10^{-n}$. We need to represent each number by its closest representation that is less than original by means of finite sum of two in negative ...
27 views

### Number of ways to choose rows with inclusion condition

I have a large collection of lists consisting of 1's and 0's, each list the same length. I call each list a row. I want to know the number of ways to select rows such that their cumulative OR results ...
84 views

### External operation: binary and unary perhaps???

Consider the following examples from which some definitions are derived: Let us take an element from the set R of real numbers (say, the number 8) and another from the set L of lengths (say, 4m). ...
109 views

### Given a binary number, how do we get the last decimal digit?

Given a binary representation of 25 i.e 11001, if I am interested only in the last decimal digit, how do I get it?
22 views

### Binary addition preserving Hamming weights

Let $x,y$ be two $n$-bit strings, with Hamming weights (number of $1$ bits) equal to $w_{1},w_{2}$, respectively. Let $z$ be the binary representation of the sum $x+y$, where we interpret $x$ and $y$ ...
247 views

### Exponential generating function for the number of binary strings of length $n$

I know that the generating function of the sequence counting the number of binary strings of length $n$ is $e^{2x}$. But my book doesn't explain why this is the case. Could you give me a little more ...
63 views

### Does a bijection from the reals to the any binary form?

It is fairly simple to store all rational numbers in a binary format (not base 2) (a language composed of only 1s and 0s, no . marking) by simply storing one integer, a seperator, and another integer. ...
73 views

### binary representation of integers congruent 1 and 3 modulo 4

Let $k=b_nb_{n-1}\ldots b_3b_2b_1b_0$ be the binary representation of an odd positive integer. Prove: If $k\equiv 1 \mod 4$ then $b_1=0$. If $k\equiv 3 \mod 4$ then $b_1=1$. I think that to prove ...
73 views

### How many bit-flips are required to achieve random distribution?

If I have a binary number W bits wide, initially all set to zero, and I repeatedly pick a random bit and toggle it from zero to one or vice versa, how many times would I need to do this to achieve ...
86 views

I'm going to discuss about Signed Number's Binary addition, I searched about it and even read books. Now I make little changes in it's logic and start my own logic to solve it. Let me show 4 bit ...
62 views

### Looking for expectation of the number of substrings

The question is formulated as follows: if we are given $n$ random binary strings of length $n$, what is the expectation of the number of substrings they have in common? Sounds pretty simple, but if ...
224 views

### Simplifying sum equation. (Solving max integer encoded by n bits)

Probably a lack of understanding of basic algebra. I can't get my head around why this sum to N equation simplifies to this much simpler form. $$\sum_{i=0}^{n-2} 2^{-i+n-2} + 2^i = 2^n - 2$$ ...
236 views

### Multiplication and binary xor

I have to prove one thing that combines logical xor and arithmetical sum of binary representation of some numbers. Could you direct me what can I read on this topic? Specifically, I need to prove ...
### What is the minimum length of maximal palindrome of a binary word of length $n$?
For example if we have $n=4$ then the minimum length of maximal palindrome is 2. Here are all four digit possible binary words along with their maximal palindromes: ...
Consider all 100 digit numbers, i.e., those between $0$ and $10^{100} - 1$ (inclusive). For each number, take the product of non-zero digits (treat the product of digits of $0$ as $1$) , and sum ...