# Tag Info

1

The simplest thing to do, especially from an algorithmic standpoint, is to do successive doubling: if $n$ is the decimal integer to be converted to binary, compute powers of $2$ using a recursive loop, at each step checking the condition that you have not exceeded $n$: So if $n = 237$, then we calculate: $$1, 2, 4, 8, 16, 32, 64, 128, 256.$$ The final ...

2

I'll give you a method and then I'll explain it. I'll use 237 to demonstrate the method. Calculate $\log_2{(237)} = 7.88\ldots$ we only care about the first digit as it tells us that $2^7$ is the largest power of 2 smaller than 237. An explanation of this is that is that the logarithm tells us what we need to take 2 to the power of to get 237. As the ...

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 ...

0

For every value, there are $t$ values different by one bit Since there are $2^t$ values, there are seemingly $2^t\cdot{t}$ such pairs But we need to divide this number by $2$ in order to eliminate duplicates So the total number of pairs differing by one bit is $\dfrac{2^t\cdot{t}}{2}=\color\red{2^{t-1}\cdot{t}}$ The total number of pairs 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 ...

0

Suppose that the integer $m$ can be written as a binary number. Find the rightmost $0$ bit in that binary number. That is, $m$ looks like $$m=\overbrace{\text{????????}}^{\substack{\text{some sequence}\\\text{of 0s and 1s}}}\overbrace{0111111}^{\substack{\text{1 zero and}\\\text{ n ones}}}$$ Then $m+1$ looks like $$... 0 Given n,q \in \mathbb{N}. Consider the recursion$$ \begin{array}{rcl} n_0 &=& n,\\ m_p &=& \lfloor \log_q n_p \rfloor \in \mathbb{N},\\ n_{p+1} &=& n_{p} - q^{\displaystyle m_p} \in \mathbb{N}. \end{array} $$Then we obtain$$ \exists k : m_k = 0 \Longrightarrow n = \sum_{\ell=0}^k q^{m_\ell}. $$What we need to prove ... 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 ... 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, ... 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: ... 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. 0 I assume \vec{u}_{k} are the remaining basis vectors? Then they are not in Span\{u_{1}, u_{2}\} and so you cannot predict their dot product with an arbitrary vector \vec{a}. 0 A generating function is straightforward to compute using the Goulden-Jackson cluster method (which is designed to solve exactly this kind of problem). A canonical reference is [Noonan-Zeilberger 1998]; additionally, [Kupin-Yuster 1998] works out an example problem in exactly the generality you're looking for. The calculation itself is easy; the post is ... 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} ... 0 You will need 480 variables of the form P01S01 to P08S60. These variables must be integer variables equal to 0 or 1. P03S40=1 means that student 40 is allocated to project 40. P03S40=0 means that student 40 is not allocated to project 40. You will need up to 5 constraints for each project. So if project 14 needs at least one programmer you need ... 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: ... 0 You're just asking for the binary representation of a number up to a precision of 2^{-p} for some p. The simplest algorithm is simply to first split into the integer part and fractional part, and then decompose each part separately. Method For the integer part, repeatedly divide by 2, each time recording the remainder but continuing with the ... 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 ... 0 Note: This answer is a supplement to the comment of @1999. Let (a_n)_{n\geq 0} denote a sequence of numbers. We can encode this information using different kinds of generating functions. Two customary variants are ordinary generating functions: \sum_{n=0}^{\infty}a_nx^n exponential generating functions: \sum_{n=0}^{\infty}a_n\frac{x^n}{n!} ... 0 No, the terms unary and binary only refer to the number of arguments taken by an operation. Usually, an operation on a (non-empty) set A is a function$$ A^k \to A  for some $k \geq 0$. An operation is said to be nullary, unary, or binary if $k$ is $0,1$, or $2$, respectively, and $k$-ary otherwise. The term external operation is rarely used, although ...

Top 50 recent answers are included