# Questions tagged [bit-manipulation]

The tag has no usage guidance.

76 questions
Filter by
Sorted by
Tagged with
59 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 ...
44 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', ...
64 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 ...
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 :- ...
123 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 ...
74 views

120 views

### Variable bytes (bit arrays) and flipping single bits?

My interest is strictly theoretical at this point, but ultimately applied. Is there any problem, theoretically, with defining a byte with m bits, and flipping single bits to connote T/F for a given ...
81 views

### Test a bit substring function

How do we test the following function? bits(bitstring, i, j) which returns a copy of the substring from i to ...
84 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 ...
42 views

### Convert (x + y = z) to propositional logic formula for 8-bit numbers

(Note: this was asked in the cstheory stackexchange, but I was told this is a more appropriate place for it.) I have three 8-bit 2's-complement numbers (X, Y, and Z). I want to find a propositional ...
503 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 ...
204 views

### algorithm - maximum pair-wise xor

Given two integers m and n where m < n find the maximum pair-wise xor sum. The question is how to choose m distinct integers from 1 to n such that using those m numbers yields the maximum pair-wise ...
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.
658 views

### UInt128 - Compute the product of two UInt128's that are each represented by two UInt64's?

I have a struct like this: struct UInt128 { UInt64 s1; UInt64 s2; } In this struct, s1 represents the highest 64-bits ...
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 + ...
40 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 ...
53 views

### Avoiding overflow when comparing between 16-bit numbers

Let's say I have a 16-bit number system. and let $a, b$ a 16-bit numbers in this system. I know that the numbers I can represent in this system are between $−32,768$ and $32,767$. Let's say I want ...
91 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 ...
368 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 ...
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 ...