# Questions tagged [bit-manipulation]

The tag has no usage guidance.

58 questions
Filter by
Sorted by
Tagged with
233 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/...
41 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? ...
23 views

### How are bitwise operators used in normalisation of floating-point numbers?

After having spent a significant amount of time googling this topic, I am still struggling to confidently answer the following question: ...
60 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. ...
25 views

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: ...
32 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 ...
86 views

### Intelligent use of XOR operator to find missing number

I've come across the following problem on leetcode & tried to solve it with the following code however there seems to be an even better solution that takes advantage of XOR. Leetcode has a ...
27 views

### How computer understand to either represent the original bits or two's complement as value?

Important note I know that this question may seem too simple for you scientists; however, here is the best place that I know to post it. Question Suppose we have an ...
156 views

### Given matrix, count paths visiting each number exactly once

We are given matrix of size at most $21$ by $21$, each number of the matrix is either $-1$, which means empty element, or integer between $1$ and $21$. Each integer may occure several more times in ...
11 views

### L-System coordinate conversion (as opposed to drawing): Extending the Hilbert Space Filling Curve

I have been reading for some time about L-Systems, and specifically the Hilbert Space filling curve. I am interested in writing a function to convert upper-triangular matrix coordinates into an 1-...
21 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 ...
152 views

51 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/...
47 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 ...
37 views

### Fundamental motivation behind the use of bits and binary representation

This is a naive question, but what makes binary representation special from a theoretical standpoint and from the standpoint of information theory? If for technical reasons building ternary computers ...
22 views

277 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 ...
752 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. ...
360 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 ...
167 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?
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 ...
35 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', ...
123 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) ...
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 ...
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 :- ...
108 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 ...
73 views

98 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 ...
36 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.
509 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 ...
65 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 ...