# Questions tagged [bit-manipulation]

The tag has no usage guidance.

54 questions
Filter by
Sorted by
Tagged with
517 views

### Converting a number from N to 0 in binary

Trying to solve this problem since 2 days. Still unable to figure out even a basic approach. Given a number $N$ in binary ($1$ to $10^5$), we need to convert it to $0$ using only 2 operations. ...
70 views

### How to distinguish between bits?

I read a post about differences between synchronous and asynchronous transmission modes. That post has a picture about how bits flows from terminal to computer in async mode. But how computer can ...
111 views

36 views

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

Could somebody please help me understand what is going on here (in plain English)? I think that $(k \mathbin{\&} 63)$ has the effect of modular division. Is that right? How are the primes encoded /...
51 views

155 views

### Count number of pairs of elements in an array whose bitwise OR is equal to a given integer

Given an integer array and an integer $k$, we have to count the number of pairs of elements from the array whose bitwise OR is $k$ in $O(n)$ time complexity. How could this be done?
60 views

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

I wonder if there are more things we can do with bits aside from NOT, AND, OR, XOR operations? I got this question from my teacher and I'm not really sure. How about bit shifting ">>"? Could we count ...
79 views

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

In a game application there is a session id assigned to each player every time they start a new session. Session id's are always unique and there can be billion users of this game. Whenever a user ...
45 views

### If XOR of n distinct numbers is ANDed over one of the number, the result would be zero

Say we Have n distinct numbers x1,x2,....xn And we xor the result xoredResult = x1^x2...^xn And if we AND(&) with one ...
262 views

### Find the bitwise AND of a subarray closest to given number

It was a question I was asked in an online assessment for a company. Please help me in this question- Given an array, $A$ of size $N$ and an integer $P$ , find the subarray $B = A[i \dots j]$ such ...
100 views

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

For an algorithm I need to be able to iterate over all bit strings where $k$ bits are flipped given a bit string with length $n$ and $n \geq k$. For instance let's say I have the bit string $1001$ and ...
40 views

### How to access the bit at a particular index? [closed]

How do I access the bit at a particular index in a number using shift operator. Say the number is $n$. Let the index be $i (i: 0 \le i < n).$ Rightmost bit is $0$. The only thing I can ...
138 views

61 views

### Dividing 2 integers with some constraints

This a problem i came across while practicing binary search. Here is the problem: Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. ...
33 views

### What are 'Butterfly Combinations' and why are they called this way?

In some scientific work describing Discrete Fourier Transform-algorithms, such as the well-known Cooley-Tukey algorithm, I came across the term 'Butterfly operations' and 'Butterfly combinations', ...
43 views

### Find the minimum N such that the sum of beauty of all numbers from 1 to N is at least X

The beauty of a number is defined as follows :- ...
953 views

### Hamming distance and parity

For an Hamming code of $n$ bit there are $k$ bit reserved for the data and $p$ bit for the parity where $p$ is the minimum integer for which the following inequation is satisfied: 2^p \geqslant p + ...
61 views

### How to solve Assigment problem on SPOJ? [closed]

Problem Link - Assign .This problem is known as assignment problem. I read few solutions Here is one and they are trying to solve it using Bit-masking and DP .I tried and thought hard to ...
32 views

### Least computationally expensive bitwise addition

I am familiar with the oft-cited method of bitwise addition using XOR and left shift for the carry, applied recursively. I was wondering if this is the least computationally expensive way to achieve ...
114 views

### If only using bit-shifts can produce a Turing-machine, or if you need more bitwise operations

So you can have One Instruction Set Computers. But typically these instructions have rather complicated underlying implementations. addition (addleq, add and branch if less than or equal to zero) ...
18 views

### Find $b$-th bit of a number $n$, with sign [closed]

Let $n\in\mathbb{Z}$ and $0\leq b\leq63$, $b\in\mathbb{N}$. Find the $b$-th bit for the number n on it's $64$ bit representation with sign. and $T$ be the number of test cases. This is my attempt: <...
62 views

### Difference in bit vectors

I have to write an algorithm for a following problem. I have a function that has 2 parameters: an array of 32 bit unsigned whole numbers - bit vectors [ARR] and distance[dist]. We need to find how ...
57 views

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

Let's say we have given two numbers $x, z$, and we need to find another number $y$ such that $x \text{ xor } y = z$. The xor ( exclusive or ) is bitwise operation: xor table . I know that this can be ...
73 views

### ip/tcp packet decoding without wireshark

How can we manually read and interpret packets properly without using wireshark? Let's say I have this data (IEEE 802.3 link): Now from the Ethernet header I know that the Destination MAC Address ...
54 views

### How “add” could be implemented in only bitshift operations

Typically, add/subtract/multiply/divide are primitive operations in an Instruction Set Architecture (ISA). I am interested to know if they can instead be implemented efficiently using only bitshift ...
338 views

### Fast searching through bitarray?

I've been thinking for some time but can't figure a way out. I have big bitarray i.e. 1000+ items of 10_000 bits strings, I'm searching them now linearly. (currently it is stored in one chunk of ...