People who code: we want your input. Take the Survey

Questions tagged [bit-manipulation]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4
votes
2answers
1k 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. ...
4
votes
1answer
48 views

Is the following Greedy algorithm to generate Gray Codes always correct?

I recently solved the basic problem of generating a n-bit Gray Code. The solution I used involved building larger-bit Gray Codes from smaller ones recursively (the solution I've seen on most websites)....
4
votes
1answer
65 views

Evaluating predicate on binary strings

Consider two unknown binary strings $$X = x_{1} x_{2} \dots x_{n^{2}}, \quad Y = y_{1} y_{2} \dots y_{n^{2}}, \quad x_{i}, y_{i} \in \{0, 1\} .$$ We may request a string $Z = z_{1} z_{2} \dots z_{n^{2}...
3
votes
4answers
2k views

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

Given an integer $x$, I need to find the largest power of two $p = 2^n$ that divides $x$ such that the remainder is zero. When $x$ is zero, the algorithm should return zero. For odd numbers, it should ...
3
votes
2answers
83 views

Right most set bit O(log N)

I tried to do the problem Find first set bit in Geeks for Geeks, and this is the code I used. ...
3
votes
1answer
78 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 ...
3
votes
2answers
914 views

Minimum XOR for queries

I was asked the following question in an interview. Given an array $A$ with $n$ integers and an array $B$ with $m$ integers. For each integer $b \in B$ return and integer $a \in A$ such that $a \...
3
votes
1answer
123 views

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

I have been given a number Y which is ($a$ xor $b$ xor $c$ xor $d$ xor $e$ ) of some numbers ($a$,$b$,$c$,$d$,$e$) and another no X. Now i have to determine if X is a xor combination of ($a$,$b$,$c$,$...
3
votes
1answer
52 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 /...
3
votes
0answers
39 views

Bridging inductive natural number and bits?

Most popular representation for the natural numbers in type systems is: Inductive nat : Set := | 0 : nat | S : nat -> nat. However, digital computers ...
2
votes
1answer
68 views

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?

From Wikipedia: A 32-bit register can store 2^32 different values. The range of integer values that can be stored in 32 bits depends on the integer representation used. With the two most common ...
2
votes
3answers
61 views

Determining the number of iterations needed to find the number of bits in an integer

I'm trying to understand the complexity/number of iterations needed to determine the number of bits in an integer. ...
2
votes
1answer
61 views

Prime checking and factorization with just bit cheking

I've read about some methods of prime factorization like here and here. However, I'm wondering: what can we do in prime factorization with just some bit manipulation and without other variables/...
2
votes
1answer
397 views

Can I simplify successive XOR operations?

I'm doing an online programming challenge where successive XOR operations are used (from codewars.com, if you don't want to create an account, here are the instructions). We have a rectangle of known ...
2
votes
1answer
36 views

Compressing a bit string when I know how many 1s and 0s there are

Say I have a 256 bit bit-string, and I know that there are 16 ones and 240 zeros. I know that this bit string can be compressed, because there are only 256 choose 16...
2
votes
1answer
24 views

Uniquely identifying bits

Query: Given $m$ unique integers smaller than $2^n$, can we keep at most $k$ the same bits of each number to uniquely identify them? Is this problem NP-Hard? For example, given the $4$ unique ...
2
votes
1answer
26 views

Names of power-of-two bit operations on bitsets that would not assume any number interpretation

Three commonly used functions when it comes to bit manipulation are : is_pow2: Checking that an integer is a power-of-two (only one bit is set): $00010000 \...
2
votes
1answer
81 views

find maximum sum of xors

we are given an Array Array size <= 10^4 . 0 <= A[i] <= 15 We need to partition the array into 4 subsets (each subset can have zero or more elements ). Take xor of each subset and sum ...
2
votes
1answer
48 views

Maximize AND on a sequence of XORs

Problem We are given 2 arrays a and b both of length n. We build a third array ...
2
votes
2answers
31 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{...
2
votes
1answer
38 views

Difference between CNOT and 2nd bit bitflip

I understand how the outcome of each is supposed to be different, but in matrix form are these gates not the same? The CNOT matrix negates the second bit regardless of the input of the first.
2
votes
1answer
297 views

For given set of integers, find and count the pairs with maximum value of bitwise or

Let's say we have given set of integers $A = \{x_1, x_2, x_3, x_4, \dots, x_n\}$, consisting of exactly $n$ values, all of them positive integers. Now the problem is to find the maximum value of ...
2
votes
0answers
213 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?
1
vote
2answers
33 views

Is there a way to store an arbitrarily big BigInt in a bit sequence, only later to convert it into a standard BigInt structure?

I am trying to imagine a way of encoding a BigInt into a bit stream, so that it is literally just a sequence of bits. Then upon decoding this bit stream, you would generate the standard BigInt sort of ...
1
vote
1answer
58 views

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

I'm wondering if there is a mathematical or computer science term for a number X such that Y | X = Y? For example: ...
1
vote
2answers
62 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 ...
1
vote
1answer
90 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 ...
1
vote
1answer
34 views

A small question about generating random variable with geometric distribution

I was reading Professor Knuth's Volume 2 (page 136) about generating a geometrically distributed random variable $N$ (with $p$ as the probability of success). Basically, the idea is to generate a ...
1
vote
1answer
55 views

How can I prove or disprove that the following function is bijection?

For a research project, I tried to prove or disprove that a function called xxhash128_low is a bijection from 64 bit unsigned integer to 64 bit unsigned integer. I have shown that it is sufficient to ...
1
vote
1answer
28 views

XOR operation to swap to value without additional variable

I'm breaking my mind to find a good explanation to split two variables with the XOR operation. The operation is the following: ...
1
vote
2answers
43 views

Simple question about signed integer multiplication

If you have a signed integer int x = any And then state that x < 0 Is the following statement true or false? ...
1
vote
2answers
53 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 ...
1
vote
2answers
466 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 ...
1
vote
1answer
122 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 ...
1
vote
1answer
41 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 ...
1
vote
1answer
117 views

Must a Turing machine tape be binary?

I once asked why does computer data bits are usually organized on binary (base 2) sets, rather than on unary (base 1) sets, aiming to also understand why its not also ternary (base 3), heptary (base 7)...
1
vote
3answers
90 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. ...
1
vote
1answer
43 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', ...
1
vote
2answers
52 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 :- ...
1
vote
1answer
1k 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 + ...
1
vote
1answer
73 views

Create binary numbers with a described pattern

I am looking for an algorithm that can create binary numbers following certain patterns. Let $n$ be the size; and assume that is a power of 2. Let $E$ be the exponent; $n = 2^E; k = \log n$. The $0, 1$...
1
vote
1answer
30 views

Book CS:APP, using bit set and bit clear

Okay so I'm going through a book CS:APP. I'm in chapter 2. And problem 2.13 talks about how the Digital Equipment VAX computer used bis (bit set) and bic (bit clear) instead of Boolean operations AND ...
1
vote
0answers
52 views

Is it reasonable to assume modern computers can do hardware math with integers up to 2^64?

I was writing up an algorithm that involved knowing the size of integers my hardware can manage without having to resort to software implementations of math operations and the additional computational ...
1
vote
1answer
148 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 ...
1
vote
0answers
35 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 ...
1
vote
0answers
173 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) ...
1
vote
0answers
19 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: <...
1
vote
0answers
79 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 ...
0
votes
2answers
207 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 ...
0
votes
1answer
1k 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/...