12 votes

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$.
user avatar
  • 7,127
10 votes
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 ...
user avatar
7 votes

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 ...
user avatar
6 votes
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-...
user avatar
  • 474
5 votes
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 ...
user avatar
  • 6,920
5 votes
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 ...
user avatar
  • 22.7k
5 votes

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 ...
user avatar
  • 937
4 votes

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 ...
user avatar
4 votes
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 ...
user avatar
  • 18.8k
4 votes

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 ...
user avatar
  • 3,318
3 votes
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, ...
user avatar
  • 33k
3 votes
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 ...
user avatar
3 votes
Accepted

How "add" could be implemented in only bitshift operations

This is impossible, a shift does not combine two operands.
user avatar
  • 3,318
3 votes
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, ...
user avatar
  • 140k
3 votes
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$ ...
user avatar
  • 14.1k
3 votes

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 ...
user avatar
  • 140k
3 votes
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.
user avatar
  • 12.3k
3 votes
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, ...
user avatar
3 votes
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 ...
user avatar
  • 1,037
2 votes

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 ...
user avatar
  • 140k
2 votes
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 ...
user avatar
  • 6,920
2 votes
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 ...
user avatar
2 votes
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....
user avatar
  • 33k
2 votes
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 ...
user avatar
  • 3,318
2 votes

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.$$
user avatar
  • 3,318
2 votes

Converting a number from N to 0 in binary

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 ...
user avatar
  • 133
2 votes

Find the bitwise AND of a subarray closest to given number

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 (...
user avatar
  • 24.9k
2 votes
Accepted

Dividing 2 integers with some constraints

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 ...
user avatar
  • 22.7k
2 votes

find maximum sum of xors

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

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