Questions tagged [bit-manipulation]
The manipulation of individual bits. Operators used may include bitwise AND, OR, XOR, NOT, left-shift, and right-shift.
7,885
questions
0
votes
1
answer
54
views
Bit masking & garbage bits
In the topic "Using the Bitwise Logical Operators" from Herbert Schildt's Java: The Complete Reference, Schildt makes the conjunction ~a & 0x0f in order to "reduce its value [~a] to ...
0
votes
0
answers
114
views
Can we replace XOR with multiply-add?
I'm working on a CUDA program where ALU is fully utilized (almost 100% compute throughput). The program does a lot of XOR operations, among others. Is it possible to offload the XOR to the floating-...
1
vote
3
answers
76
views
How can I efficiently generate all N-bit values with M set bits, and the corresponding bit-reversed values?
I'm using the following Python code to generate all values with popcount set bits among bits total bits:
def trailing_zeros(v):
return (v & -v).bit_length() - 1
def bit_permutations(popcount, ...
0
votes
0
answers
38
views
Why isn't an (intentional) overflow occuring in my python FizzBuzz implementation?
I noticed that two out of three of the values generally associated with FizzBuzz are one less than a value of 2n, and that made me want to try an implementation where it uses overflows instead of ...
0
votes
1
answer
76
views
How can I perform XOR between every elements of two 2D numpy arrays by saving the memory usage efficiently?
I am not familiar with XOR operations and I was wondering if there is an efficient way to perform XOR operation for every elements between two 2D NumPy arrays by saving the memory usage.
Here is my ...
0
votes
1
answer
39
views
How to unpack bits from packbits results?
I am not familial with np.packbits and I want to perform a huge XOR operation by using it.
Here is my toy example:
import numpy as np
# Example arrays
u_values = np.array([[True, True, True, True, ...
1
vote
0
answers
61
views
How to use AtomicInteger with bit flags to atomically check two values in Java in one safe operation without a synchronized block?
I saw that question: question
Unfortunatelly I don't understand how to use AtomicInteger with bit flags to atomically check two values (as mentioned by @Radiodef in his answer) in Java.
Could somebody ...
2
votes
3
answers
161
views
How to interleave two uint32_t values into one uint64_t?
If I have two 32-bit values, X and Y, how can I efficiently interleave their bits into one 64-bit value Z, in the order xyxyxyxy... (Z is a position on a Z-order curve.)
I could iterate over each of ...
0
votes
1
answer
159
views
What is the runtime of using bit manipulation (XOR and AND) to perform binary addition?
Apparently you can bit manipulation to perform binary addition. This is the Python code for it:
class Solution:
def addBinary(self, a, b) -> str:
x, y = int(a, 2), int(b, 2)
...
0
votes
0
answers
16
views
How do I represent a 32 bit binary by using 8 characters?
I'm looking at memory addresses which are 32 bits. How do I represent them using 8 digits/characters - such as '0x12345678'?
How many bits does each character represent? What is this system called?
...
-2
votes
0
answers
52
views
Why do I get incorrect results of these bit shifts? [closed]
This may not be normal bit shifting, but I am trying to put two numbers side by side such that their bits are unchanged.
d0 = 245678916563
d1 = 783623571345
b = 1000000000000
dx = int(hex(d0)[2:]....
3
votes
1
answer
246
views
is there a non-iterative way of finding the index of the Nth set bit? [duplicate]
#include <cassert>
#include <cstdint>
uint64_t pos_of_nth_bit(uint64_t X, uint64_t bit) {
while (X) {
if (!bit--)
return __builtin_ctzll(X);
X = X & (X - 1);
}
...
0
votes
2
answers
137
views
Divide by variable power of 2 using assembly
I've got this task:
dividePower2
Compute x/2n, for 0 ≤ n ≤ 30. Round toward zero.
Argument 1: x
Argument 2: n
Examples:
dividePower2(15,1) = 7
dividePower2(-33,4) = -2
This is what I've got so ...
0
votes
2
answers
92
views
Encode a std::uint64_t into vector of floats
I have to do some dirty trickery and pass a std::uint64_t around an application. Unfortunately I am limited to using a std::vector<float> for that.
To my understanding float is 32-bit on most ...
-1
votes
1
answer
97
views
How do I find 4 complementary 24bit RGB colors with no overlapping bits?
I am seeking four colors that are distinguishable, somewhat complementary/visually appealing, and share no bits in common. What I mean by this is as follows:
Consider only the first 24 bits of a u32 ...
4
votes
1
answer
57
views
No intrinsics for x86 BMI instructions BLSI & BLSR in Clang?
I wanted to try out some intrinsics for the x86 BMI set. The grep bmi /proc/cpuinfo shows both bmi1 and bmi2 in my AMD Ryzen CPU. But I cannot get clang to compile some of the instructions, in ...
1
vote
1
answer
109
views
Setting/getting 1-bits of __m256i vector from integer array of bit positions
Setting bits:
Given an array int inds[N], where each inds[i] is a 1-bit position in [0, 255] range (and all inds[i] are sorted and unique), I need to set corresponding bits of __m256i to 1.
Is there a ...
1
vote
0
answers
48
views
Pushing tiles using bitboards and bit operations
Am am currently coding up a somewhat chess-like game that includes a "pushing" mechanic. Getting an efficient algorithm for this seems to be elusive.
Here are the details. I represent an NxM ...
1
vote
1
answer
121
views
Manipulating float bits using unions: Finding the correct uint type that fits the float
In C, I’ve seen this code used as a way to manipulate a float, down to the bits:
union {
uint32_t bits;
float value;
}
By defining a variable of this type, one can perform bitwise operations ...
0
votes
0
answers
28
views
How can I deal with float IEEE 754 and uint/int at the same time using Node js Buffer?
Hello everyone: I have to parse some data with some format that involves uint, int with sign and float trying to optimize the using of bytes. I think I can handle decently with uint/int numbers ...
0
votes
1
answer
66
views
78.LeetCode/Subsets problem - Solution accepted using helper function, but Memory Limit Exceeds otherwise [closed]
I was trying to solve LeetCode medium question Subsets [link (https://leetcode.com/problems/subsets/) using Bit manipulation technique.
First I implemented solution as follows :
class Solution {
...
0
votes
1
answer
52
views
Rotating bits in a byte in Java
I am trying to implement right_encode found in the SHA 3 specifications. https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-185.pdf
enter image description here
The specific part I am ...
-2
votes
2
answers
61
views
Can one emulate bitwise arithmetic "and" or "or" using only non-bitwise operations?
Imagine we are tasked with using an idealized scientific calculator which has the following properties:
no direct support for bitwise operations, or for base conversions (eg cannot simply "...
0
votes
4
answers
107
views
whether the binary representation of a number is alternating bits eg. 10101010 , 1010 etc
So I had to find whether the binary representation of a number is alternating 1s and 0s.
Expected time complexity and space complexity are both O(1)
My Idea was first to find the 1's complement of the ...
2
votes
0
answers
55
views
Hashing a list of 64 bit int so list[n] % len yields unique values in range 0:len-1
The title may leave something to be desired, my apologies. The best I could come up with.
My initial idea was to "simply" shuffle the bits of a given list of 64 bit integers in a way so that ...
1
vote
0
answers
46
views
Large integer implicitly truncated to unsigned type [-Woverflow] warning in bit mask
While creating a bit mask to set a bit in 8-bit register, I encounter this warning, but I can't see what can be wrong here:
static const uint8_t sck_pin_n_mask = ~(1 << SCK_LCD_PIN);
...
0
votes
1
answer
39
views
Golang producing weired result for bitwise not operations
package main
import "fmt"
func SingleZeroBitAtRightMostOneBitPosition(n int) int {
return ^n | (n - 1)
}
func main() {
fmt.Println(SingleZeroBitAtRightMostOneBitPosition(128))
...
0
votes
2
answers
89
views
Python Bitwise Operations Extremely Slow
I have a formula that relies on bitwise operations that I have written (see below). I wish to loop over 3 dimensions and apply that formula to each tuple to generate a key.
However, the below code ...
0
votes
1
answer
110
views
Fast __m256i bit operations - find or clear highest or lowest set bit
I am looking for fast code to perform the following operations on __m256i and would appreciate help:
Clear least significant bit (least significant that is set)
Clear most significant bit (most ...
2
votes
1
answer
101
views
Bitwise weighted sum for the QOI index hash function
I recently contributed to a Rust library for the QOI image format. As part of the encoding process, the encoder keeps track of an array of already seen RGBA pixel values. It calculates the index using ...
0
votes
1
answer
823
views
Find the number of special subarray such that the bitwise XOR of first and last element is equal to XOR of all the other elements in the subarray
Given an array of integers, find the number of subarray which has length at least 3 where the bitwise XOR of first and last element in the subarray is equal to rest of the elements in the subarray. ...
-1
votes
1
answer
65
views
How to check redundant value using Bitwise AND and bitwise NOT Operator? [closed]
I have got a below snippet of code to check the RAM redundant value using bitwise Operator
uint16 initial_value = (uint16)(myvalue_32bit & 0xFFFFu);
uint16 toggle_value = ~((uint16)(myvalue_32bit ...
-1
votes
2
answers
212
views
Another way to implement < in C
I'm having trouble writing the correct code to return 1 + x if x < 5, return 1 otherwise.
Problem specifications:
Return 1 + x if x < 5, return 1 otherwise (this ensures that 1 <= f(x) <= ...
3
votes
4
answers
128
views
How to change 1 to zeros in the binary form in C
I can't figure out how to change any consecutive 1 to zeros in the binary form of x (consecutive 1 means a set of 1 that contains more than one 1).
Problem specifications:
Allowed operators: ! ~ & ...
-1
votes
4
answers
131
views
How to make bit wise XNOR in C
I'm having trouble writing a bitwise XNOR function with at most 7 ~ and | operators. Example: bitXnor(6, -5) = 2. How do I do this without &?
So far I have this:
int bitXnor(int x, int y) {
...
0
votes
1
answer
60
views
How do I create a sliding window of 5 bits in a single byte?
Here is a visual of what I want to have happen 5 bit sliding window
In words, I want a sliding window of 5 bits. I need to store a history of 5 events within a single byte. I'm using the 5 most ...
-1
votes
2
answers
68
views
how to perform bit wise "or" operation with same value/ variable?
I am trying to understand bitwise operation that took place in same variable within itself.
let's say i have 2 variable x which is 4-bit reg type,
if i write
w_out<=(|x); you can take value of x as ...
1
vote
3
answers
164
views
Generate all n-bit numbers where the i-th bit is 0
I need to generate all 2^(n-1) n-bit numbers where bit i is always 0 and j is the index of the number in the theoretical list of possible numbers, in ascending order. Here is a simple table for when i ...
-7
votes
1
answer
105
views
Parsing of bits with XOR and Complement
I have a problem to locate the number which occurs only once when all other numbers in the vector occur exactly thrice.
class Solution {
public:
int singleNumber(vector<int>& nums) {
...
0
votes
1
answer
100
views
getting error in applying bitwise AND in C Sharp [closed]
I am trying to translate the below from C++ to C# where v is an unsigned long:
(v & 1UL) ? 0x9908B0DFUL : 0x0UL
The above had no problem in C++. But when I put the same in C# (v being ulong):
(v &...
0
votes
0
answers
54
views
Datasheet says EEPROM address is 0xA0 but it worked for me on 0x50. Is there a particular reason to right-shift bits?
I read the device data of the SFP Optical Transceiver module using it's EEPROM. This image shows that the EEPROM's address is 0xA0, but it didn't work for me. It worked when I entered the address as ...
0
votes
2
answers
85
views
How to bit shift left or right based on sign of int?
I need to bit shift x by b, where b can be positive (shift left), zero (nop), or negative (shift right).
C bit shift doesn't handle negative shifts.
Can I define an inline func or macro to do this? ...
0
votes
1
answer
21
views
bitwise shift output a wrong result
I am finishing my Informatics assignment and I wrote these for my question:
Create a variable s with a value of 154 and a variable p with a value of 6. Display its values in decimal and binary form on ...
0
votes
1
answer
88
views
How can I generate a signed 32 bit Integer from a UUID and salt string?
I do not know my bit-twiddling well enough and could use some help.
I'm looking to generate a number to use as a 1-time "communication channel" between 2 different scripted agents to sync up ...
2
votes
2
answers
71
views
Perl to set/reset 8th bit on string
Given a string, I want to
set all chars from A fo I's 8th bit on (0x41 ~ 0x49 to 0xC1 ~ 0xC9).
reset all chars that has the 8th bit on to off.
Like,
$s='@ABCDEFGHIJKLMNOPQRS';
$s1= join "",...
1
vote
3
answers
153
views
How can I perform a branchless conditional arithmetic operation in C?
I have a value int x where I want to conditionally add (for example) a value int y to, contingent on bool c. I could write code like this:
bool c; // C23, or stdbool.h macro for _Bool. Converts to ...
0
votes
0
answers
32
views
Most efficient way to get Least Significant not set bit and Most Significant not set bit
I have a binary string, say 10111101111 and I want the Most significant not set bit i.e the first 0 starting from the left and the Least significant not set bit i.e. the first 0 from the right.
...
-2
votes
2
answers
89
views
Functionality difference between num = 1 << 4 and num |= 1 << 4
So if I understand bitwise operations correctly, num = 1 << 4 shifts the 1 to the left 4 places by adding 0's to the lsb side of the number and if there's 1 in the way it changes to 0.
But if I ...
1
vote
1
answer
79
views
Extracting the Last N Bits from an Array of Bytes in C
I have an array of unsigned characters in C:
unsigned char array[] = { 0xF0, 0xCC, 0xAA, 0xF0};
/* Represented as binary: 11110000 11001100 10101010 11110000 */
I'd like to extract the last N bits ...
7
votes
1
answer
136
views
Is this bitwise conversion safe?
I have a situation where I need to pack 16 bits into a 64-bit number and later read them back as a signed integer in the range [ -32768, 32768 ). The method I have chosen for this is to compute the ...