# Tag Info

6

It might be easier to ask how many bit strings of length $n$ do not have the substring '01'. I think of the bit string as a little plot, so $0100$ would be the graph $(0,0),(1,1),(2,0),(3,0)$. The substring $01$ corresponds to an upward jump in the graph. It follows that the only graphs that do not have an upward jump are those of the form $1^* 0^*$ (of the ...

6

Computing the decomposition of a nonnegative integer into sums of powers of $2$ is essentially determining the binary (base-$2$)-representation of a number. For example, we can decompose $42$ as $$42 = 32 + 8 + 2 = 1 \cdot 2^5 + 0 \cdot 2^4 + 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 = 0 \cdot 2^0,$$ so in binary we write $42$ in bits (the binary analogue of ...

4

Let the number whose base 2 floor you want to find be $N$. We want to find the greatest $k\in \mathbb{Z}$ such that $2^k \leq N$. Take the base 2 log of both sides to get $k \leq \log_2{N}$. Since we want the maximum value of $k$ that still fulfills this inequality and that is an integer, we pick $k = \lfloor \log_2{N} \rfloor$. Then you just need to compute ...

4

Easier way to answer this: there are $2^{12}$ bitstrings. How many bitstrings don't have a substring $01$? To answer this: This means that a bitstring has to be either all $0$s, all $1$s, or has $n$ leading $1$s and $12-n$ following $0$s. (Like $100000000000$ through $111111111110$.) There's only one bitstring that's all $0$s, and there's only one bitstring ...

4

This all boils down to the concept of positional notation. For example, consider the number $19$ (in base $10$), which in base $2$ becomes $10011$. To understand why, you need to understand what this notation mean: $$19_{10} = \color{lime}{1}\color{green}{0}\color{olive}{0}\color{grey}{1}1_2 := 1 \cdot 2^0 + \color{grey}{1} \cdot 2^1 + \color{olive}{0} ... 3 A simple explanation turns on the apparent randomness of the base-b digits of sufficiently large powers of two, in the sense that they tend to behave like random samples. (However, this leaves the apparent randomness unexplained.) Thus, let S_k denote the multiset of digits appearing in the numeral of 2^k, and let n_k be their number; i.e., n_k = ... 3 The critical observation is that a string that lacks the substring 01 can only be a (possibly empty) substring of 1's, followed by a (possibly empty) substring of 0's. If any 1 comes after any 0, then there must be a 01 substring. Therefore, there are only 13 different bit strings that fail to have a substring 01, and the total number of ... 2 There is the relationship (a\wedge b)\oplus (a\vee b) \oplus (a\oplus b)=0 which holds for all a and b. Or, equivalently, any two of a\wedge b, a\vee b, and a\oplus b will produce the third upon combining with \oplus. 2 I would attack this problem from left to right: Let's suppose that my string starts with 0, then we have a lot of possibilities that my string have the substring 01, those are (2^{11} - 1) (we have all the 2^{11} possibilities, except when all the 11 bits left are all 0s). The next step I would take is supposing that my string starts with 10, then we ... 2 Here's a description of an imperative algorithm to do the job. I am being naughty about numeric analysis and just testing real numbers for equality. I will leave you to worry about that. Let x be the input and put r = 1. Now there are three cases: If x < 1, then divide r by 2 until r \le x, r is now the result; If x = 1 then r is ... 2 Every integer form 1 to 2^n-1 is expressible using the sums of the numbers 1,2,4,8, ... 2^(n-2), 2^(n-1), and no other numbers. This can be proven using induction. 2 For searching leetcode "Bitwise AND of Numbers Range" I reached here, use a long long or python integer doesn't have integer overflowing problem, while if you want to try to use C with regular 32bit signed integer, you've chosen the hard way I got finally figured out a solution, wonderful for embedded board running environment, this uses the least storage ... 1 Divide by 8, then write the remainder in the far right octal place. Take the quotient of the prior division and divide it by 8, then write the remainder in the next octal place to the left. Repeat step 2 until you achieve a quotient of 0, and write the remainder in the next octal place to the left. Ta da! 1 I’ll get you started. Start at the bottom: the leaves have empty subtrees, so the value of each leaf is simply the integer stored in it. Now go up a level and work on the four max nodes just above the leaves. each of them is the root of a small tree with 3 nodes. For the first one, for instance, we have this tree: 0 / \ ... 1 Do you already know the answer to this question? You really should indicate that if you do. I presume the microbiologist determines the 7-bit representation of the sample number, and sends all samples with the highest-order bit set into vial 1, the second-highest-order bit into vial 2, and so on, with those samples with the lowest-order bit set into ... 1 One of the faster and simpler methods is exponentiation by squaring. It is based on taking advantage of the fact that an integer power can be easily reduced by dividing the power by two (possibly with remainder):$$ a^b = a^{\left \lfloor \frac{b}{2} \right \rfloor 2 + b \% 2} $$where \left \lfloor \frac{b}{2} \right \rfloor denotes the integer ... 1 PolynomialQuotientRemainder[x^22+x^18+x^17+x^14+x^12,x^8+x^2+x+1,x,Modulus->2] {x+x^2+x^7+x^8+x^9+x^10+x^14,x+x^4+x^7} Update for move to math: Well, now that it's here, the Mathematica answer doesn't seem quite as useful anymore. The answer is that you use the same long division you learned in elementary school. The only difference is that now ... 1 The number of strings with the first 01 occurring at the 1st position: 01XXXXXXXXXX Therefore, it is 1\cdot2^{10} The number of strings with the first 01 occurring at the 2nd position: 001XXXXXXXXX 101XXXXXXXXX Therefore, it is 2\cdot2^{9} The number of strings with the first 01 occurring at the 3rd position: ... 1 Reducing exponentiation to squaring and occasional multiplication seems to be fast, see Exponentiation by Squaring. It uses$$ x^n = \begin{cases} x \, ( x^{2})^{(n - 1)/2}, & \mbox{if } n \mbox{ is odd} \\ (x^{2})^{n/2} , & \mbox{if } n \mbox{ is even}. \end{cases}  The squaring is done by $x^2 = x * x$. In Henry S. Warren's "Hacker's Delight", ...

1

Here's a reference that I found: http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method The most intuitive algorithm that I can think of for squaring binary numbers involves appending zeros and adding. As an example, say you want to square $101101$. To do so, note the position of each $1$ in the number (this can be done ...

1

Attach a zero to each side of each $1$, then insert the $m$ "$010$" units into a line of $(n-2m)$ zeroes (including potentially before and after). This is possible in ${n-2m+1 \choose m}$ ways. Clearly we need $(n-2m+1) \ge m \implies m \le \frac{n+1}{3}$ Algorithmically, finding positions for the $m$ $1$s can use the above insertion process as follows: ...

1

Hint: Whatever the first $N-1$ bits are, the probability that $X$ is odd is $\frac{1}{2}$.

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