Tag Info

Hot answers tagged

5

Here's an example, which can be easily expanded to the general case. Let's say we want to write $21$ as the sum of distinct powers of two. ("Distinct" meaning that they're all different.) Well, if we drop the distinctness condition, it's easy: $21=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1$ Let's try to clean this up a bit. We don't need more than one $1$, ...


4

From right to left, the binary place values (mod 10) are $1, 2, 4, 8, 6, 2, 4, 8, 6, \dots$. You can add the reduced (mod 10) place values with $1$s in them, and then mod your answer by ten. In your example, $11001$, you would add $8 + 6 + 0 + 0 + 1=15\equiv 5 \pmod{10}$.


3

The "standard" answer is (a). Two's complement is created to preserve arithmetics in binary, so that you can add positive and negative numbers using the same ALU's. Adding the Two's complement representations of -x and x always gives the first power of 2 greater than the bit-width of the representation, thus truncating to zero.


3

You're probably familiar with the idea of "base $10$" representation of integers. That's our normal decimal system. We write $275$ to stand for $2(10^2)+7(10^1)+5(10^0)$. In base $10$, the digits $0,1,\ldots,9$ occur as multipliers of powers of $10$, and the products are added up to give the number in question. The same sort of thing is possible for any ...


2

The number $7$ is the first number (other than $1$) that is not the sum of two powers of $2$. However it is the sum of three powers of $2$, $$7=2^2+2^1+2^0$$ If we allow sums of any combination of powers of $2$, then yes, we can get any natural number. (That is what makes binary representations possible.) You can get an easy proof by strong induction: ...


2

If $n = 2$ or any even integer not one less than a perfect square, you will need infinite digits to the right of the decimal point. In all cases you will need $1 + \Big\lfloor\dfrac{n+1}{2}\log_2\Big(\dfrac{n+1}{4}\Big)\Big\rfloor$ digits to the left of the decimal point. Let $d_r = $ digits needed to right of decimal point. $d_r = \begin{cases} ...


2

The exclusive-or of two $n$-bit patterns that differ by $k$ bits is an $n$-bit pattern with $k$ ones and $n-k$ zeros. Thus, after choosing the first $n$-bit pattern, there are $\binom{n}{k}$ patterns which differ by $k$ bits. With Replacement Since there are $2^n$ different $n$-bit patterns, the probability that two $n$-bit patterns differ by $k$ bits is ...


1

There are $2^t$ possibilities. The favorable cases are when only one bit is different. For the first time it doesn't matter, what you choose. For the second time this one different bit can be located on $t$ different places, if $t$ is the length. So the probability is: $$\frac{t}{2^t-1}$$ $2^t-1$ because after you choose the first number, after that you ...


1

Because the base $b$ representation of a number is "invertible". Let a number be $$n=\sum_{i=0}^dd_ib^i,$$ where $b$ is the base and the $d_i$ are the digits, such that $0\le d_i<b$. For example, $$443_5=4\cdot5^2+4\cdot 5+3=123.$$ By the remainder theorem, there is a unique quotient $q$ and a unique remainder $r$ such that $$n=qb+r\text{, and }0\le ...


1

The best description of this process I have seen (in terms of clarity) comes from Howard Eves' Introduction to the History of Mathematics: If we have a number expressed in the ordinary scale, we may express it to base $b$ as follows. Letting $N$ be the number, we have to determine the integers $a_n,a_{n-1},\ldots,a_0$ in the expression $$ ...


1

Choose any integer $b$ such that $b\geq 2$. Choose some integers $d_k,d_{k-1},\ldots,d_1,d_0$, each of which satisfies $0\leq d_i<b$, and define $n$ to be $$n=d_k\cdot b^k\;+\;d_{k-1}\cdot b^{k-1}\;+\;\cdots\;+\;d_1\cdot b\;+\;d_0$$ (In other words, define $n$ to be the base-$b$ number $(d_k\ldots,d_1d_0)_b\;$.) Recall what the division algorithm says: ...


1

I found this paper http://cs-people.bu.edu/evimaria/papers/kdd127-gionis.pdf which indicates that your problem is indeed #P-complete, (if you look at it as a set-cover problem, which is easy to do, your 0 and 1 just say whether the given index is in the subset encoded by the row, and you want to cover all indices with a choice of subsets, i.e. rows), and ...



Only top voted, non community-wiki answers of a minimum length are eligible