# Tag Info

5

If the computer starts in the middle of the stream, it has no way to know—it will be completely confused. Fortunately, that's not how the protocol works. The computer and terminal have to sync up before they can communicate. There are a few different ways of doing that, but once they're in sync (which includes agreeing on how long each 1 or 0 should last), ...

4

Suppose that your numbers are $n$-bit long. Then you can think of them as elements of the vector space $\mathbb{F}_2^n$. The number $X$ can be written as an XOR of $a_1,\ldots,a_m$ if $X$ is in the linear span of $a_1,\ldots,a_m$. In order to determine whether $X$ is in the linear span of $a_1,\ldots,a_m$, you can use Gaussian elimination.

3

Using Trie Data Structure, you can solve this problem in $O(m + n)$ if we know that values are computer integers (e.g. all 32-bit or 64-bit values). Let say we know that all integers in $A$ are 32-bit values. Use the following steps: Create an empty trie. Every node of trie may contains at most two children for 0 and 1 bits. Insert all values in $A$ into ...

3

If you think about it, there are $2^4 = 16$ possible ways of combining two bits to give a single-bit ouput (AND, OR, NOR, NAND, XOR, ...). Can you work out what they all are? This is because there are four possible input combinations ($00$, $01$, $10$, $11$) and any subset of those can be mapped to~$1$. But we could combine more than two bits to give a ...

3

This is impossible, a shift does not combine two operands.

3

Access into a bit array is constant time. In particular, if you have an array that is stored contiguously in memory, indexing into the array takes constant time: reading $A[i]$ takes constant time, regardless of how large $i$ is. That's all that you need to do to access a bit array. In particular, if you have an array of bytes, then you can read the $i$th ...

3

One can observe that, for any boolean values $a,b,c$, we have $a=b$ if and only if $a \text{ xor } c = b \text{ xor } c$. (To prove that we note that $\Rightarrow$ is trivial, and $\Leftarrow$ follows by xor-ing with $c$ once more and applying the cancellation law.) Hence, the equation $x \text{ xor } y = z$ is equivalent to $(x \text{ xor } y) \text{ ... 2 If you want to look for an exact match, use a hashtable. Choose a hash function that hashes a 10,000-bit string to a short hashcode. This approach will be simple and highly efficient: the running time will basically be the time to compute the hash of the 10,000-bit value that you are searching for. 2 Popcount is going to be your best option here. As j_random_hacker mentions in a comment, popcount on a single word can be done in$O(\log W)$time if implemented by hand, or$O(1)$if the machine provides a dedicated opcode for it (which should take a constant number of clock cycles—but then again,$W$should also be a constant for any given machine). (Note:... 2 Let your initial bit string be x. For all numbers b with k bits set (i.e. where k bits are 1), output x xor b. Finding all numbers with k bits set is described elsewhere, for example here 2 P is in big-endian format. P0 —0111011011010011001011010010011001011001010010001011011010000001, The first bit, 0, means 2*0 + 1 = 1 is not a prime. The second bit, 1, means 2*1 + 1 = 3 is a prime. The third bit, 1, means 2*2 + 1 = 5 is a prime. The fourth bit, 1, means 2*3 + 1 = 7 is a prime. The fifth bit, 0, means 2*4 + 1 = 9 is not a prime. The sixth ... 2 Contrary to what you think, extracing bytes by shifting and masking is completely unrelated to the storage order (both little-endian and big-endian storage schemes exist and don't influence the results). An int variable is represented by 32 bits. The least significant byte is made of the eight least significant bits and you obtain them by i & 0xFF 0b ... 2 Xoring is "reversible":$y$xored by$x$flips the bits of$y$where$x$has ones. Xoring one more time restores the initial value. $$(y\oplus x)\oplus x=y=z\oplus x.$$ 2 For every$i \in \{0,\ldots,n\}$(where$n$is the length of the array) and for every$a,b,c \in \{0,\ldots,15\}$, we determine whether it is possible to partition the first$i$elements of the array into four subsets, the first three of which XOR to$a,b,c$, respectively. We also compute the XOR of the entire array. Using the information for$i = n$, we can ... 2 This can be done by running an AND between n and a number with it's ith bit set to 1, which can be obtained by 1 << i. The result of this operation will be zero if the ith bit in n is zero, or 1 << i otherwise. Case of zero: n = 10111 m = 01000 (1 << 3) n & m = 00000 Case of one: n = 10111 m = 00100 (1 << 2) n &... 2 I think you can just do a simple breadth-first-search on this. First note that: There's only one way to do move #1 (you can perform move #1 in one place, if it's at all possible), and doing it multiple times wouldn't result in a loop. It doesn't make sense to do move #2 twice in a row. The important thing to do while searching is to note whether the number ... 2 Let f (i, j) = AND ($A_i, A_{i+1}, ..., A_{j-1})$for$0 ≤ i < j ≤ n$.$f (i, j)$has the property that whenever$i ≤ i' < j' ≤ j$,$f (i, j) ≤ f (i', j')$. We also have$f (i, j)$= AND($(f (i, k), f (k, j)$) for any$0 ≤ i < k < j ≤ n$. Because of these properties, we get an algorithm slightly better than brute force as follows: Keep track ... 1 Well, the fact is that binary values are much easier to handle technically that ternary values. And there are reasons for it. So if there was some technical breakthrough where suddenly ternary values become easy to handle, there would be a good reason to believe that binary values would have a similar breakthrough very soon. So yours is a purely ... 1 You can think of a bitvector as a set, by giving names to the various bits. For example, if we name the bits in an 8-bit integer using the numbers$0,\ldots,7$(where$0$is the LSB and$7$is the MSB), then$00010010$is the same as$\{1,4\}$. Your first function asks whether the set has size$1$. If we name the bits using numbers as above, the second ... 1 Here is a strategy (I will only consider positive numbers): Let$d$be the dividend and$x$be the divisor. Generate all values$x_i = 2^i x$, up to some some$x_k$such that$x_{k+1}$exceeds the dividend. This can be done with only one addition per value since$x_{0} = x$and, for$i \ge 1$,$x_i = x_{i-1} + x_{i-1}$. Similarly, generate all values$b_i = ...

1

Let us enumerate the students $s_1, \dots, v_n$. Let $A$ be the set of students and $B$ the set of subjects. Moreover, let $S_i$ be the set of subjects the student $s_i$ likes. The dynamic programming table will be $C\left(A, 2^B\right)$, where $C(s_i, S)$ says in how many ways we can assign the subjects in $S$ to the first $i$ students. Note that if $|S| \... 1 Yes, there are ways to improve the efficiency greatly. Let${}_k{i}$be the$k$-th digit of$i$in binary representation, i.e., it is 0 if$\lfloor i/2^k\rfloor$is even and 1 otherwise. For example, since$19=(10011)_2$,$_019=1$,$_119=1$,$_219=0$,$_319=0$,$_419=1$. In most programming languages,${}_k{i}$can be computed as$(i\text{>>}k)\%2$. ... 1 First, we have some basic observations: The minimum number of steps to convert$N$to$0$equals to the minimum number of steps to convert$0$to$N$. To convert$0$to$N$, the optimal way would be to apply Operation 1 and 2 alternatively. Now consider the bit sequence$b_1\ldots b_m0$. After performing Operation 1 and 2 alternatively, we get $$b_1\ldots ... 1 So, a summary of the Wikipedia page on Butterfly Diagrams: In Computing Science, a Butterfly is the portion of a computation that combines the results of (two) smaller computations into the larger one. This is common in Discrete Fourier Transformation algorithms, as well as in the otherwise unrelated Viterbi Algorithm for finding the most likely sequence of ... 1 Notations : b(x) is the beauty of x. S_c(n) = \sum_{x = 0}^{2^n-1} (b(x)+c) where c\in\mathbb N \tilde O(\log t) : polylogarithmic in t Argument : Let's first show that S_c(n) is easy to calculate for any c,n\in\mathbb N. Each number in [\![0, 2^{n-1}]\!] has at most n bits, and for each i\in[\![1, n]\!], exactly half of the numbers ... 1 You can obtain a formula in CNF form by writing down a truth table (with 2^{24} rows) and then converting each row to a single clause. This will yield a formula with 2^{24} clauses, but the method is straightforward. If you want a shorter formula, I suggest using logic synthesis, e.g., Quine-McClusky, Espresso. The usual path to get a small formula is ... 1 If the numbers have width c\log n then there is a randomized O(n^{2-1/O(\log c)}) algorithm that finds the maximum OR correctly with high probability. The idea is to find the maximum OR bit by bit, MSB to LSB. We can do this using c\log n queries of the following form: "Is there an OR whose k most significant bits are b_1\ldots b_k?". Each such ... 1 IMO, no sensible answer can be given without some knowledge on the distribution of the bits in those keys. It might very well be that the first, say, 32 bits of the keys are completely discriminant and sorting or hasing on these will do the trick, with no need for full comparisons. It could also be that the 600 first bits are always the same and this would ... 1 The controlled NOT gate is represented by the matrix$$ \begin{pmatrix} 1&0&0&0\\ 0&1&0&0\\ 0&0&0&1\\ 0&0&1&0 \end{pmatrix} $$In contrast, the matrix corresponding to negating the second bit is$$ \begin{pmatrix} 0&1&0&0\\ 1&0&0&0\\ 0&0&0&1\\ 0&0&1&0 \end{pmatrix}... 1 It depends what operations are available to you for 64 bit integers. The product of two 64 bit integers is a 128 bit integer. Many programming languages don't provide such a product, for example in C you will likely have an operation that produces the 64 bit (x * y) modulo$2^{64}\$, but not an operation that produces the 128 bit number x * y. On the ...

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