# Tag Info

79

This works not only for $16$, but also for any other power of $2$. Maybe an easy way to see it is to look at base $10$ instead of base $2$. Say I want to write the number $12345678$ in base $100$. Of course we don't have $100$ symbols to express single digits in base $100$, so we can write them using base $10$: $[0],[1],[2],\ldots,[99]$. Then $$... 31 Let's define a notation for "base 1000" where the every "base 1000 digit" consist of a three-base10-digits group. Thus, the base-10 number 123456789 would read 123 456 789 in base 1000. As you can see, conversion between these is really, really simple. The reason is that a certain number of digits in the lower base exactly represent a digit in the higher ... 30 A preliminary observation: in base 10, multiplying a number by a power of 10 amounts to shifting the digits leftward:$$ 10^3\cdot148=1000\cdot148=148000. $$The analogous statement is true in any base. In what follows, numbers without a subscript are base-10; otherwise, the subscript indicates the base:$$ \begin{aligned} 256\cdot ...

19

As you mentioned, $$6 = {\color{red}1}\cdot 2^2+ {\color{red}1}\cdot 2^1+{\color{red}0}\cdot 2^0 = {\color{red}{110}}_B.$$ Analogously $$\frac{1}{4} = \frac{1}{2^2} = {\color{red}0}\cdot2^0 + {\color{red}0}\cdot 2^{-1} + {\color{red}1}\cdot 2^{-2} = {\color{red}{0.01}}_B.$$ Edit: These pictures might give you some more intuition ;-) Here $\frac{5}{16} = ... 15 No, it is not possible. In general, there is no algorithm that compresses every$n$bit string, or reduces the length of a random string of bits (in expectation). Your algorithm may compress some numbers but then it will use more memory to store others. If your data is random, there is no benefit in using your compression scheme. Actually the fact that no ... 14 If you look at the "column headings" for binary, they are$\dots 256, 128, 64, 32, 16, 8, 4, 2, 1.$Compare these with those for base$16$:$\dots, 256, 16, 1.$The crucial thing is that all the base 16 headings are present in the base 2 case. Similarly, converting between base 9 and base 3 would be really easy for the same reasons. 13 Yes. What you are doing is known as working in the$2$-adic numbers. The$2$-adic numbers are equipped with a curious notion of distance given by the$2$-adic metric. In this metric, two numbers are close together if their difference is divisible by a large power of$2$. In particular, large powers of$2$are very small. So relative to the$2$-adic metric ... 11 The number$n$must be even. The string is determined once we choose the places where the$n/21$'s go. These$n/2$places can be chosen from the$n$available in$\dbinom{n}{n/2}$ways. Things look nicer if we let$n=2m$. Then the number of strings of the type you want is$\dbinom{2m}{m}$. This is equal to$\dfrac{(2m)!}{(m!)^2}$. In your special case ... 10 There is at least one instance of a$0$followed by a$1$. Remove these two numbers, find (by induction hypothesis) a good starting point for the reduced circle, put the$0$and$1$back in and use the same starting position. It is easily verified that this is a valid starting position. It is also not difficult to show the result without induction: A person ... 8 For each bit (binary digit) that you have, there are two possibilities: Either it can be a zero, or it can be a one. Therefore, if you have one bit, you have two possible numbers. If you have two bits, each of them can be either a zero or a one, and since there are two possibilities for the first, and two possibilities for the second, there are$2^2 = 4$... 7 That works as$16 = 2^4$is a power of$2$. We have for a number$n\in \mathbb N$written in hexidecimal digits as$n = (s_k\ldots s_0)_{16}$, that is $$n = \sum_{i=0}^n s_i 16^i$$ writing$s_i \in \{0,\ldots, 15\}$in binary as$s_i = (b^i_3\ldots b^i_0)_2that is $$s_i = \sum_{j=0}^3 b^i_j 2^j$$ that n = \sum_{i=0}^n s_i 16^i = \sum_{i=0}^n ... 6 \begin{align} &&17539=2\cdot8769+1\\ &&8769=2\cdot4384+1\\ &&4384=2\cdot2192+0\\ &&2192=2\cdot1096+0\\ &&1096=2\cdot548+0\\ &&548=2\cdot274+0\\ &&274=2\cdot137+0\\ &&137=2\cdot68+1\\ &&68=2\cdot34+0\\ &&34=2\cdot17+0\\ &&17=2\cdot8+1\\ &&8=2\cdot4+0\\ ... 6 So, to interpret your question, you have two different procedures for filling out a table of numbers which has a definite top and left edge, but continues indefinitely down and to the right. First is Don't fill in any cell before all the positions directly above and directly to the left of it are filled. Write in each cell the smallest nonnegative ... 6 Every number has a binary representation n = \sum_{i=0}^m b_i 2^i, \qquad b_i \in \{0,1\}, $$for an appropriate m. For example,$$ 10 = 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0. $$Here are some hints on how the algorithm works: How can you tell whether b_0 = 0 or b_0 = 1? Suppose that (b_k \cdots b_0)_2 is the binary ... 5 You are absolutely right : the exact number is 56, and it can be shown rigorously as follows. By Post’s theorem, a boolean function is not expressively adequate iff it is either monotone, affine over \frac{\mathbb Z}{2\mathbb Z}, self-dual, truth-preserving or falsity-preserving. In three variables this simplifies considerably. Indeed, not being truth- ... 5 Divide the 2^n strings into two groups, one with an odd number of zeros and one with an even number of zeros. If you take anything from the "odd" group, and flip the first bit, you will get something in the "even" group. Similarly, flipping the first bit of anything in the "even" group will produce something in the "odd" group. Once you realize that ... 5 The recurrence can be written$$c_{n,k}=c_{n-1,k}+c_{n-1,k-1}+[n=k=0]-[n=1][k=0]+[n=k=1]\;,$$where the square brackets are Iverson brackets; this makes the recurrence valid for all n,k\ge 0 on the assumption that c_{n,k}=0 if either n or k is negative. This is an easy way to build the initial conditions into the recurrence, and although I’ve not ... 5 The number of bits required to represent an integer n is \lfloor\log_2 n\rfloor+1, so 55^{2002} will require \lfloor 2002\; \log_2 55\rfloor+1 bits, which is 11,575 bits. Added: For example, the 4-bit integers are 8 through 15, whose logs base 2 are all in the interval [3,4). We have \lfloor\log_2 n\rfloor=k if and only if k\le\log_2 ... 5 Since you tagged "binary" in your question, you might also want to recall that Karnaugh map is a standard way to map inputs to outputs with just complement, AND and OR gates. (Or "~", "\&" and "|" bit-wise operators in C) For example, you can define a,b,c to be bits at position 2,1,0 here to use the map. If you draw out the map, this is what it ... 5 Let the positions be a_{i,j}, where 1\le i,j\le 4. You can fill the 3\times 3 square in the upper lefthand corner, i.e., positions a_{i,j} with 1\le i,j\le 3, any way you like. Once those 9 positions are filled, there is exactly one way to fill the remaining 7 positions to get an even number of 1’s in each row and column. Can you see why? ... 5 According to "Distribution of the figures 0 and 1 in the various orders of binary representation of kth powers of integers", W. Gross and R. Vacca (Mathematics of Computation, April 1968, 22, #102, 423–427), the answer is yes. On page 423 they define a function N_k(h), which is the count of 1 bits in the hth position of the sequence n^k over one of ... 5 A starting point for a divisibility test (by 5) in binary would be the observation that 2^4\equiv1\pmod5. Therefore also 2^{4n}\equiv1\pmod5 for all natural numbers n. From that point on it is quite similar to the familiar "casting nines" method of testing divisibility by nine in base 10. For example:$$ ... 5 $$101110 - 110111 = 101110 + 001001 = 110111$$ with110111$being in two's complement (since it has a leading$1$, hence, equivalent to binary$-001001 \; = \;-1001$The trick I use to go back and forth from two's complement is to switch ALL digits (reverse$1\to 0, 0 \to 1$, then add one bit$1$($+000001$in this case) 5 FACT ONE: Each position in positional number systems is an increment-by-one in power of the base. Take the decimal number "one-hundred and twenty-three": Base-10: 1 2 3 | | \ | | "ones" (10^0) | "tens" (10^1) "hundreds" (10^2) Base-16: 7 A | \ | "ones" ... 4 It's based on this fundamental principle: If, for a given choice there are$n$options, and for every choice of the first there are$m$options, then there are$mn$options for both choices. This easily extends to more than two choices. So for the 32 bits mentioned, there are 2 choices for each bit. For each choice of the first bit, there are 2 for the ... 4 The required value should be the following:$$\sum_{i=0}^{x-y}\binom{x}{y+i}$$ This is because you need to select$y, (y+1), ..., x$positions from the total$x$positions to place$1$'s, and the rest zeroes. This expression is just a sum of the last$y$binomial coefficients. As far as I know, there is no general expression for the sum of$k$binomial ... 4 As a teacher and tutor who's often introduced binary to students with good results, I found this question intriguing, so I did a little research on the US (I can't speak for other countries). The closest thing to a nationwide US mathematics K-12 curriculum is the common core state standard for mathematics (also see the Wikipedia article for background) ... 4 It is in fact obvious from the diagram. The number on the left is the divisor, while the number at the top is the quotient, and CRC is the final remainder. In long division, every time you successfully subtract a multiple of the divisor, that (single digit) multiplier goes in the quotient above the right hand digit of the multiple of the divisor. In ... 4 You go for that subtraction exactly as you would do for decimal, except that you need to borrow already for$2=$10. So for your example, you have 100 - 001 <- place for borrows ___ So you start in the rightmost column, where you have$0-1$. Since$0<1$, you have to borrow from the left, so you have 10-1 that is$2-1$which is$1\$. So after ...

4

IEEE 754 single precision is a standard used to represent floating-point numbers in base 2 on 32 bits. Every representable floating-point number has a representation of the form: $$\underbrace{\fbox{c_1}}_{\pm} \ \underbrace{\fbox{c_2 c_3 c_4 c_5 c_6 c_7 c_8 c_9}}_{E} \ \underbrace{\fbox{c_{10} c_{11} c_{12} \cdots c_{31} c_{32}}}_{m-1}$$ where ...

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