Questions tagged [bit-manipulation]
The bit-manipulation tag has no usage guidance.
65
questions
1
vote
1answer
14 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
1answer
51 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 ...
3
votes
1answer
37 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)....
1
vote
0answers
51 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
59 views
How to prove that n&(n-1) and n&(-n) respectively returns and removes the least significant bit?
In a code, I saw someone use:
n&(n-1) to get the least significant bit of n ⇒ 101000 will return 1000
...
3
votes
2answers
81 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.
...
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:
...
0
votes
0answers
38 views
Efficient triangular decomposition of an integer
Euclidean division is an iterative process
that has been made super-efficient at the CPU level, right?
Its specification is that if I do (q, r) = f(n, d), I get ...
2
votes
1answer
60 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 ...
1
vote
2answers
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?
...
0
votes
1answer
46 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:
...
2
votes
3answers
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.
...
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
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 ...
0
votes
2answers
197 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 ...
1
vote
0answers
29 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 ...
0
votes
0answers
13 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-...
2
votes
1answer
22 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 ...
0
votes
1answer
152 views
Maximum value of $\{ i \land n \mid a \leq i \leq b \}$
I was doing problems in "Leetcode" and found a problem that I could not solve.
Given a non-negative number $n$ and two non-negative numbers $a$ and $b$, consider every number $i$ such that $a \leq i \...
0
votes
3answers
119 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 ...
0
votes
1answer
798 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/...
2
votes
2answers
30 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
54 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/...
1
vote
2answers
49 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 ...
3
votes
2answers
721 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
62 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}...
0
votes
2answers
39 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 ...
1
vote
1answer
22 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 \...
1
vote
2answers
69 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
124 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 ...
2
votes
1answer
73 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 ...
1
vote
0answers
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 ...
3
votes
1answer
118 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$,$...
2
votes
1answer
330 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 ...
4
votes
2answers
941 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. ...
1
vote
2answers
382 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 ...
0
votes
2answers
164 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 ...
2
votes
0answers
208 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
0answers
139 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)
...
0
votes
2answers
56 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 ...
1
vote
1answer
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', ...
1
vote
2answers
61 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
2answers
45 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
115 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 ...
0
votes
0answers
74 views
Find xor sum of all pairs raised to power of 3
We are given array $A$ of $N$ integers each in the range $1 \leq A_i \leq 2^{30}$, that is we can write each integer with at most 30 bits. The target is to compute $\sum_{1\leq i \leq N,1\leq j<i} (...
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:
<...
3
votes
1answer
41 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
1answer
74 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 ...
0
votes
1answer
815 views
Bytes from integer using bitwise operators
So I am extremely confused with using bitwise shifts used to extract the bytes from an integer. I find that if I do something like this...
...
0
votes
2answers
112 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 ...
