# Tag Info

13

You just need to count the number of $0$ at the end of the binary encoding of $x$.

10

After reading through your question carefully, it is clear that this is not actually the Find First Set-operation as others have answered as Find First Set would give you the largest value $n$ for which $p = 2^n$ is a factor of your number, whereas what you where asking for was the corresponding $p$. This is good as the final step from your question to FFS ...

8

Your operation is known as find last set, count trailing zeroes, bit scan forward, and possibly other names. Many modern CPUs support it natively. On Wikipedia you can find several fast implementations.

6

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

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

5

This really depends on your computing platform and how your integer is represented (and how big it might be). If we're talking about an integer which fits into a single register of your real-world computer, then as @YuvalFilmus writes, there are often assembly language instructions like "find first set" or "count trailing zeros" which ...

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.

4

My guess is that what you are seeing is a Level 2 Ethernet frame and therefore the preamble is missing. Also the Ethernet checksum seems to be missing. In this case everything seems to line up (the packet type inside the Ethernet frame, the IPv4 version, the IPv4 packet length, the packet type, i.e. TCP, inside the IP packet, ...). Then you'd read your ...

4

Questions about programming are off-topic, however there are a few computer science questions hidden in here: what n & -n does, and how floating point is represented. The n & -n operation isolates the rightmost bit of a word in two's complement arithmetic. This is a very useful operation to know about. Consider, for example, the following 8-bit word: ...

3

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

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{ ... 3 Given any specific candidate divisor$d$, it is easy to check whether$d$is a divisor of the number (the standard modular reduction algorithm is a generalization of those tricks you mentioned). This can be done for all$d$. However, it doesn't help with efficient factorization, because there are exponentially many candidate divisors, so trying each one, ... 3 I would say that$X$is a subset of$Y$, in terms of bits set. 3 The contents of a register don't have any inherent semantics. Some instructions might assume certain semantics. For example, the x86 ADD instruction assumes that the registers represent integers, either unsigned or signed using two's complement. There are signed and unsigned versions in the x86 architecture for the multiplication instructions. Another ... 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 It doesn't work, for example if x2 = 0 then xoredResult & x2 = 0 all the time no matter what else the set of numbers contains. Or for an other example, the set { 1, 2, 3 } xors to zero (so it ANDed by any of its members, or even anything else, yields zero) but contains no repeated elements. 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 ... 2 Your problem is NP-hard. To see this, you can reduce it from the minimum test cover (or test collection) problem: given a set$X$of$\ell$elements and a collection$C = \{C_1, \dots, C_k \}$of$k$subsets of$X$, find a minimum test cover for$X$and$C$, i.e., a subset$C'$of$C\$ that has minimum size and satisfies the following property: for every pair ...

2

Look at Elias delta or gamma coding as an example.

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