Questions tagged [bit-manipulation]
The bit-manipulation tag has no usage guidance.
80
questions
0
votes
1
answer
68
views
What property of XOR makes this algorithm work?
I'm having trouble figuring out why using XOR for this problem works; I've done it a couple of times by-hand, and can't really seem to understand it. I know that XOR is commutative and associative, ...
1
vote
3
answers
313
views
How bits translated into text on the screen?
recently i started studying computer science and computer graphics, and one question really haunts me. Mby someone can explain this. How bit patterns become translated into (for example ) text. I know ...
1
vote
0
answers
32
views
Efficient bit-level implementation of Boolean polynomials with few variables
A Boolean polynomial in $n$ variables $x_1, \dots, x_n$ is an expression of the form
$$\sum_{\mathbf{s} \in \{0,1\}^n} c_{\mathbf{s}} x_1^{s_1} \cdots x_n^{s_n}, \quad \text{ where } c_s \in \{0,1\} .$...
- 11
0
votes
1
answer
68
views
Number of subsequence's with same values of bitwise and, or and xor
GeeksForGeeks
We are given an array arr of $n$ element. We need to count number of
non-empty subsequences such that these individual subsequences have
same values of bitwise AND, OR and XOR. For ...
-2
votes
1
answer
47
views
What is the reason for this contradiction about the size of the char type?
the size of one char in C is 4 bytes, however to define an 'A' character we use the sum of two values like this expression here:
or in other way i want to say that the char is 4 bytes size, but in ...
1
vote
2
answers
58
views
Why is the time complexity of the Bit Manipulation solution to Binary Addition O(M + N)?
I am trying to understand why the time complexity of the Bit Manipulation solution (https://leetcode.com/problems/add-binary/solution/) to the Binary Addition problem is O(M + N), where M and N are ...
- 125
0
votes
2
answers
349
views
Complexity of `n & (n - 1)` should be O(1) or O(log n)?
I'm looking at the methods posted in https://www.geeksforgeeks.org/program-to-find-whether-a-no-is-power-of-two/ for checking whether n is a power of 2.
Method 5, ...
- 133
1
vote
1
answer
35
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 ...
- 285
0
votes
1
answer
71
views
Shuffling Bits For Uniform Distribution
I am writing a hashing algorithm to be used in the key-value data store. That is for each key the location of the data is determined. The structure of the data store is given a key, a value needs to ...
- 265
2
votes
1
answer
52
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 ...
- 23
3
votes
4
answers
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 ...
- 174
0
votes
1
answer
286
views
while loop for bitwise conversion program
int counter(char c){
int count = 0;
while (c!=0){
if((c & 1) !=0)
count++;
c = c >> 1;
}
}
I am trying to understand a ...
- 167
0
votes
0
answers
22
views
What is the order of magnitude of bitwise operations involved in a SHA-256 hash?
Specifically, how many bitwise operations (approximately, could be just order of magnitude) occur each time a Bitcoin ASIC miner performs a SHA-256 hash in typical mining computation, i.e. as it ...
- 1
2
votes
1
answer
101
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...
- 133
1
vote
1
answer
100
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$...
- 11
1
vote
1
answer
344
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)...
- 25
1
vote
1
answer
55
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 ...
- 13
1
vote
1
answer
73
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 ...
- 352
4
votes
1
answer
75
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)....
- 425
1
vote
1
answer
85
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 ...
0
votes
1
answer
126
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
2
answers
98
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.
...
- 53
1
vote
1
answer
34
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:
...
- 45
0
votes
0
answers
63
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 ...
- 195
2
votes
1
answer
145
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 ...
- 23
1
vote
2
answers
59
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?
...
- 11
-1
votes
3
answers
251
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
3
answers
66
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.
...
- 31
1
vote
1
answer
59
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:
...
- 113
1
vote
2
answers
39
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,871
0
votes
2
answers
836
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 ...
- 111
0
votes
0
answers
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 ...
- 101
2
votes
1
answer
34
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,376
0
votes
1
answer
155
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 \...
- 47
0
votes
3
answers
168
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 ...
- 9
1
vote
1
answer
2k
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/...
- 167
2
votes
2
answers
35
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{...
- 131
2
votes
1
answer
129
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,055
1
vote
2
answers
89
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 ...
- 111
3
votes
2
answers
1k
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 \...
- 33
4
votes
1
answer
80
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}...
- 41
0
votes
2
answers
62
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 ...
- 209
2
votes
1
answer
27
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 \...
- 209
1
vote
3
answers
136
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.
...
- 159
1
vote
1
answer
183
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 ...
user109308
2
votes
1
answer
122
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 ...
- 103
1
vote
0
answers
49
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 ...
- 121
3
votes
1
answer
135
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$,$...
- 31
2
votes
1
answer
546
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 ...
- 23
4
votes
2
answers
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. ...
- 41