Tag Info

New answers tagged

1

If the leading bit can't be zero, then neither can the last bit. So you can represent an $11$-bit binary palindrome as follows: $$1\ b_1\ b_2\ b_3\ b_4\ x\ b_4\ b_3\ b_2\ b_1\ 1$$ where $x$ can be either $0$ or $1$, and $b_1b_2b_3b_4$ is any $4$-bit number. It follows that there must be $32$ numbers of this form. A $10$-bit palindrome will follow the same ...


0

If you want to round a single-precision floating point value down to the next power of 2, you can do this (as long as the number is "normalized", which it always is unless it's infinity, NaN, or extremely small) by making all the significand bits zero. Something like this would probably work: float truncateSgand(float value) { return (float) ((uint32_t) ...


-1

Practical insight Floor of base two is nothing but the floor of a binary number. Floor of base 10 gives floor of decimals . let's see examples $$ floor_{10} 15.3=15$$ In binary- $ floor_2 110$(decimal equivalent 6)$=100$ (decimal equivalent 4) so to do this function first convert it into binary then take only the left most 1 and put the rest as 0's For ...


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


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


0

Converting $X$ into base $K$, building up the representation $R$ from the right: $R$ is blank, ($i=0$) Find $d_i \equiv X\bmod K$ and subtract $d_i$ from $X$, prefix $d_i$ to $R$ If $X$ is $0$, $R$ is complete - exit Divide $X$ by $K$, (increment $i$), go to step 1. $R$ ends up as $d_n\ldots d_1d_0$ Random example with $K=8$ Convert 45676: $ ...


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!


0

as logicians are allowed to discuss before the game begins, they decide that every alternate man will shout the color of the logician just before him, now if the color of the logician's hat who is being questioned is the same as the one of the hat of the logician in his front, he will be saved too otherwise the logician just before him is saved. but if they ...


0

Binary to decimal: $$0.010101\implies 1\times 2^{-2}+1\times 2^{-4} + 1\times 2^{-6}$$ Decimal to binary, for example, $0.15$: $$0.15\times 2=0.3$$ The integer part is $0$, this is your fist bit in binary number. $$0.3\times 2=0.6$$ The integral part is $0$ again, second bit. $$0.6\times 2=1.2$$ The integral part is $1$, third bit. $$0.2\times ...


0

The way to read a binary expansion of this form is completely analogous to the way you would read a 'decimal expansion.' Example: $35.12 = 3\cdot 10^1 + 5\cdot 10^0 + 1\cdot 10^{-1} + 2 \cdot 10^{-2}$. Analogously, $0.010101 = 0\cdot 2^0 + 0 \cdot 2^{-1} +1 \cdot 2^{-2}+0 \cdot 2^{-3}+1 \cdot 2^{-4}+0 \cdot 2^{-5}+1 \cdot 2^{-6}$. Note that the "." just ...


0

Well, just as the digits after the decimal point in base-10 are the tenths place, hundredths, thousandths and so on, the digit after the point in binary is the $1/2$s place, $1/4$, $1/8$, etc. So $$0.010101_2=\frac{1}{4}+\frac{1}{16}+\frac{1}{64}=0.328125_{10}$$ To get a binary number from a real number in base 10, you would divide the number by ...


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


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


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.


1

The number of strings with the first $01$ occurring at the $1$st position: $01XXXXXXXXXX$ Therefore, it is $1\cdot2^{10}$ The number of strings with the first $01$ occurring at the $2$nd position: $001XXXXXXXXX$ $101XXXXXXXXX$ Therefore, it is $2\cdot2^{9}$ The number of strings with the first $01$ occurring at the $3$rd position: ...


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


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


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


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


0

Hint: Consider the $1$'s in the top string fixed and count the number of ways to place the $1$'s in the lower string. There are $10,000-20$ bits which are unknown. Of those exactly $20$ are $1$'s. There are $\binom{10,000-20}{20}$ ways to put those $1$'s into the bottom string. Each of those placements are equally likely... and only 1 of those lines up ...


0

There are $\binom Mk$ permutations of $k$ ones and $M-k$ zeroes. This is clear because this corresponds to the number of ways one can chose $k$ elements in a set of $M$, these elements being the positions of the ones. Now consider the rows $x$ and $y$. They contain the value of $x^{\text{th}}$ and $y^{\text{th}}$ elements in the different permutations. If ...


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


0

<?php function UniqueRandomNumbersWithinRange($min, $max, $quantity) { $numbers = range($min, $max); shuffle($numbers); return array_slice($numbers, 0, $quantity); } for( $i=0 ; $i < 20 ; $i++ ){//20 instances $numbers = UniqueRandomNumbersWithinRange(0, 204-1-3-9+1-2*10, 10);//204 events sort($numbers); ...


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

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


0

And if you want to square (or multiply) very large numbers, there is the Karatsuba algorithm: http://en.wikipedia.org/wiki/Karatsuba_algorithm


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


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


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

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


0

I don't see where the "desired degree" comes into your question. Leaving that aside, there is further the issue of what coefficient ring you are intending to use -- it seems like $\mathbb{F}_2$ would be most appropriate, but maybe you mean $\mathbb{Z}$. For now I'll assume that you are working over $\mathbb{Z}$. The first step is to create the ...


1

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


0

There's no need to guess: \begin{align} 120&=2\cdot 60+0\\ 60&=2\cdot 30+0\\ 30&=2\cdot 15+0\\ 15&=2\cdot 7+1\\ 7&=2\cdot 3+1\\ 3&=2\cdot 1+1\\ 1&=2\cdot 0+1 \end{align} So $$ 120=\texttt{1111000}=0\cdot1+0\cdot2+0\cdot4+1\cdot8+1\cdot16+1\cdot32+1\cdot64 $$ If you want to use eight bits, then you can pad with zeros on the left: ...


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


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


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



Top 50 recent answers are included