# Tag Info

### How to find the largest power of two divisor of a given integer?

You just need to count the number of $0$ at the end of the binary encoding of $x$.
• 7,127
Accepted

### How to find the largest power of two divisor of a given integer?

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

### How to find the largest power of two divisor of a given integer?

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 ...
• 269k
Accepted

### Minimum XOR for queries

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-...
• 474
Accepted

### How to distinguish between bits?

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 ...
• 6,920
Accepted

### ip/tcp packet decoding without wireshark

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 ...
• 22.7k

### How to find the largest power of two divisor of a given integer?

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

### Is is possible to determine if a given number is xor combination of some numbers?

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 ...
• 269k
Accepted

### Right most set bit O(log N)

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 ...
• 18.8k

### How bits translated into text on the screen?

On machines with a CRT, this was implemented in the display hardware. As the line scanning took place, the value of the character at the row/column position was obtained from RAM, and that value was ...
• 3,318
Accepted

### Can I simplify successive XOR operations?

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, ...
• 33k
Accepted

### What kind of operations can we do with bits?

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 ...
• 80.1k
Accepted

### How "add" could be implemented in only bitshift operations

This is impossible, a shift does not combine two operands.
• 3,318
Accepted

### How to retrieve reset bit in constant time in a bit array

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, ...
• 140k
Accepted

### Easiest way to find y in $x \text{ xor } y = z$ with given $x \text{ and } z$

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$ ...
• 14.1k

### Prime checking and factorization with just bit cheking

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 ...
• 140k
Accepted

### Is there a name for X when X bitwise OR Y is Y?

I would say that $X$ is a subset of $Y$, in terms of bits set.
• 12.3k
Accepted

### If the integer representation used is "0 through 4,294,967,295 (2^32 − 1)", so does this mean the register cannot handle negative numbers?

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, ...
• 269k
Accepted

### How bits translated into text on the screen?

Most often, bits are not translated into text. They are translated to RGB colours pixel by pixel on a framebuffer found into RAM. The colours will be arranged pixel by pixel to make it look like a ...
• 1,037

### Fast searching through bitarray?

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 ...
• 140k
Accepted

### How to count number of 1s of the first k positions in a bitset (bitmap)?

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 ...
• 6,920
Accepted

### Given a bitstring generate all bitstring with n flipped bits

Let your initial bit string be x. For all numbers b with k bits set (i.e. where ...
• 2,296
Accepted

### How are the prime numbers encoded in Knuth's example of fitting primes into memory cache?

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....
• 33k
Accepted

### Bytes from integer using bitwise operators

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 ...
• 3,318

### Easiest way to find y in $x \text{ xor } y = z$ with given $x \text{ and } z$

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.$$
• 3,318