# Questions tagged [bit-manipulation]

The tag has no usage guidance.

92 questions
Filter by
Sorted by
Tagged with
1 vote
40 views

### Efficient way to implement a bit-wise counter that becomes 1 every (k*n)+i times

My question is about LeetCode "137.Single Number II": 137.Single Number II Given an integer array nums where every element appears three times except for one, which appears exactly once. ...
• 131
56 views

### Is there an algorithm to implement N-input-gates using smaller gates?

To borrow part of a description from a similar but distinct question: there exist 2^(2^N) different functions which accept N binary inputs and return a 1 bit output. For the purposes of my question I ...
1 vote
48 views

### Splitting a Larger Unsigned Integer into Summable Parts

I have a very strange (arbitrary) problem that I have been trying to wrap my head around, but have been struggling to figure out how to accomplish this. I'll use Rust but in a pseudo-code fashion, ...
• 379
116 views

### Why is 2's complement used for representing negative numbers?

So I was reading the use complement operation in the digital logic and found, it is used to give additive inverse of the number and subtracting a number (like we do) is difficult for computer. So it ...
• 142
36 views

### Exact Definition of simple bit pattern?

I didn't find an exact description for this, but I know that any integer type is a simple bit pattern, it seems to me that the simple bit pattern should have a more exact description as I understand ...
1 vote
71 views

### Faster finding of a subset of bits with all combinations in the bitstrings

Assume that I have a bunch of bitsets (strings on $\{0,1\}$) of the same length, e.g.: 101110001 001001101 010101010 101001001 101010101 I want to find the largest ...
• 345
107 views

### Find Number of subsequences such that bitwise OR is same as sum

Suppose there is an array having at most 10 elements between 1 to 10^18. Suppose the array has elements B1,B2,.Bn. We can choose sequence A1,A2,A3,..An such that 0<=Ai<=Bi. Count How many ...
• 1
4k views

### Calculating XOR of all numbers from 1 to n: Why does this method work?

Given a number n, the task is to find the XOR of every number from 1 to n. Why does the following algorithm work? Find the remainder of n by moduling it with 4. If rem = 0, then XOR will be same as n....
• 89
128 views

### Is "Bitwise Complement Operator" (~ tilde) distributive?

To be more precise, Is ~(a+b) = ~a + ~b? Here, "~" bitwise NOT operator. I ran into this question while thinking about ...
70 views

### Number of bit string interpretations correct?

Suppose you are given a bit string $B[1 ... n]$. Now, suppose that some bits are just padding bits conveying no information, the rest of the bits may be permuted and some meaningful (that is, non-...
154 views

### Identify the missing number in a set given its superset

Given a set B and B’s superset A, if B is missing 1 number (let’s y) but don’t know which number it is, how to find that number? That is, B’ = B \ {y}, for some unknown element y B = A \ {x}, for ...
52 views

### Why is the file size smaller than what I calculated?

The question is the conversion from an animation to a video file with the following attributes: Frame rate:24 fps Resolution:320*240 pixels Color depth:24 bits Length of video: 60s Bit rate: 500kbps I ...
• 105
112 views

### What property of XOR makes this algorithm work?

I'm having trouble figuring out why using XOR for this problem works; I've done it a couple of times by-hand, and can't really seem to understand it. I know that XOR is commutative and associative, ...
1 vote
424 views

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

recently i started studying computer science and computer graphics, and one question really haunts me. Mby someone can explain this. How bit patterns become translated into (for example ) text. I know ...
1 vote
46 views

• 47
184 views

### Minimum number of ways to write a string

Consider the following question There are K magical pens (numbered 1 through K). You are given strings P1,P2,…,PK (each of which consists of characters from 'a', 'b', …, 't') ; for each valid i, the ...
• 9
1 vote
4k views

### ip/tcp packet decoding without wireshark

How can we manually read and interpret packets properly without using wireshark? Now from the Ethernet header I know that the Destination MAC Address should be at the 5th byte (after converting bits/...
• 167
36 views

### Data structure for or-lookups over bit-field associations maps

For a mapping between a bit-arrays and values I want cheap lookups using bitwise-or instead of equality. Slightly more formally, I have a set of associations $k_i \mapsto v_i$ where \$k_i \in \mathcal{...
• 131