8,023 questions
4
votes
3
answers
176
views
How to do a simple swap of two half of a 32bit integer in c?
I am trying to figure out a code that would be able to swap the higher half and the lower half of the binary form of an integer number such as for example:
0000000 00110011 01001001 11111110 turn into ...
0
votes
2
answers
124
views
How can I store Huffman-encoded bits into a truly compressed binary file in Java?
I'm building a Huffman compressor in Java.
I already have: The original text, the Huffman code table (Map<Character, String>), and the order of character appearance.
My current goal is to write ...
- 19
-1
votes
3
answers
97
views
Python Bit Shifting [closed]
Assume I have a 1 source variable (int) which is 10 bits long. Let's call it src.
I have 2 destination variables (int) which are 8 bits long namely byte1 and byte2.
MSB LSB
src ...
- 25
19
votes
9
answers
3k
views
How to clear specific byte values inside a 64-bit value without looping
Suppose I have this value, with underscores for clarity:
0x12_23_45_09_45_11_23_10
I want to zero out all instances of 0x10, 0x23 and 0x45 inside it, making this number:
0x12_00_00_09_00_11_00_00
Is ...
- 631
2
votes
2
answers
222
views
Bitwise division in C : Programme seems to work for other numbers but when the divisor is 0 it returns 11 for no apparent reason
I am trying to solve the problem posed in this question which asks that division of two numbers be performed in a bitwise manner. So, I wrote the following functions.
sum() adds two numbers.
larger() ...
- 469
5
votes
3
answers
283
views
Finding the bigger number using bitwise operation in C
I am trying to write a computer programme that will take two numbers from the user as inputs and will print the bigger number using bitwise operation. I want it to end the programme and return 1 if ...
- 469
5
votes
1
answer
255
views
"Repacking" 64 to 40 bits in AVX2
I have an array of 64-bit words, which I need to compact by removing the most significant 24 bits of each 64-bit word. Essentially this code in pure C:
void repack1(uint8_t* out, uint64_t* in) {
...
- 3,000
6
votes
4
answers
266
views
How to unpack a buffer of 12-bit values into an array of normalized float32
A measurement system (in our lab) produces data of 12 bits per sample in a packed format, i.e. 2 samples of 12 bits each are packed into 3 bytes:
buf[l + 2] | buf[l + 1] | buf[l + 0]
7 6 5 ...
- 163k
-4
votes
2
answers
104
views
Is there a name for the high and low bits of a hex string?
In the hex byte A1 B2 C3 D4, ABCD would be the most significant bits of each pair, and 1234 would be the least significant. I find that these groups of bits are often operated on together in hardware-...
- 6,566
3
votes
2
answers
189
views
Programme works but says "warning: integer constant is so large that it is unsigned", solution?
I am trying solve the problem posed in this question that asks << 1 operation be performed on a 64 bit number using NAND operation only and without using any arithmetic operation. My attempted ...
- 469
2
votes
1
answer
198
views
Why do bit manipulation intrinsics like _bextr_u64 often perform worse than simple shift and mask operations?
I'm working on performance-critical code and experimenting with different ways to extract bit fields from 64-bit integers. I expected that using intrinsics like _bextr_u64 (Bit Field Extract) would be ...
2
votes
1
answer
183
views
Fast bithacked log2 approximation
In order to estimate entropy of a sequence, I came up with something like this:
float log2_dirty(float x) {
return std::bitcast<float>((std::bitcast<int>(x) >> 4) + 0x3D800000)) -...
- 20.5k
-3
votes
2
answers
127
views
Bit Manipulation [closed]
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int main(void) {
int v;
int sign;
sign = -(v < 0);
printf("%d", sign);
}
Why ...
- 9
5
votes
2
answers
209
views
Inconsistent bitwise shifting result in C code
I'm writing a C program and need to create a bitwise mask that could potentially fill a computer word (64 or 32 bits) with all 1s. I found a bug in my code but I can't make sense of it because when I ...
- 53
2
votes
1
answer
254
views
Difficulty in understanding the logic behind a problem based on bitwise computations
As part of a test I was given, I am required to code the instructions below:
A function F(x) is defined over integers x >= 0 as:
F(x) = ∑ [(x | i) - (x & i)] (summation ∑ is over i),
with i ...
- 1,664
-2
votes
1
answer
119
views
How to perform bitwise operations on very large integers in Python with only built-in modules [closed]
I'm making an implementation of the SHA-1 algorithm in Python for a school project. My code breaks because it generates an integer too large for my school's IDE to handle.
***I only have access to ...
- 19
-1
votes
1
answer
179
views
Counting the number of set bits
this is the problem(counting bits)from cses i have attached the link here https://cses.fi/problemset/task/1146/
the goal of the problem is to calculate the number of set bits in all the number from 1 ...
- 11
17
votes
7
answers
707
views
Efficient AVX2 implementation of a 17x17-bit squaring operation with result truncation
I am trying to create an efficient AVX2 implementation for a 17x17-bit truncated squarer that returns the 15 most significant bits of the result. This operation appears as a building block in ...
- 27.1k
0
votes
1
answer
64
views
bit manipulation for big data processing with complex boolean logic
Looking into solving a very large data set problem by using bit manipulation to reduce compute
Imagine billions of records that look like this(but more than 20k in length):
Questions : A,B,C,D
...
- 31
1
vote
1
answer
80
views
Grouping bits based on binary mask [duplicate]
I am looking for an algorithm to group bits from byte A based on mask (or tap) from B, on byte C, starting from least-significant. By way of example, the mask/tap (B) has bits 1,3,4 set to 1, which ...
1
vote
0
answers
63
views
How does xz's BCJ filter for ARM64 work with the ADRP instruction?
I was trying to understand the BCJ ARM64 filter in xz here,
(also the 7zip version for reference)
I don't understand the case for the ADRP instruction, this is the snippet for it from xz:
else if ((...
- 11
0
votes
0
answers
87
views
Select a value uniformly at random from a BitSet<usize>
I have a BitSet<usize> in my simulation program which I need to select a random value from. Currently I have implemented this as follows:
/// Returns a random element from the given set.
fn ...
- 15.5k
9
votes
3
answers
334
views
3D Morton code computation utilizing carry-less multiplication
This question arose specifically in the context of exploratory work for RISC-V platforms which may optionally support a carry-less multiplication instruction CLMUL. It would equally apply to other ...
- 27.1k
5
votes
3
answers
341
views
efficient check whether unsigned integer value belongs to either of two compile-time constant intervals
In various contexts I have faced the issue of determining whether a given unsigned integer value belongs to either one of two non-overlapping intervals, and not infrequently these checks introduce ...
- 27.1k
1
vote
2
answers
110
views
Why does 32-bit bitmasking work in Python for LeetCode "Single Number II" when Python ints are arbitrary precision? [closed]
I'm trying to understand why the following solution for LeetCode's Single Number II works in Python:
class Solution:
def singleNumber(self, nums: List[int]) -> int:
number = 0
...
0
votes
1
answer
165
views
can someone explain me this x+y = x^y + 2*(x&y) how does this hold good
x+y = x^y + 2*(x&y), so here why are we multiplying it with 2, here we are trying to figure out why an addition is equal to xor or the 2 numbers and then the multiplication of x&y but ...
- 41
0
votes
1
answer
163
views
Using SQL Server, looking to get subnet from IP address and subnet mask stored in the database
We have a use of subnets for doing geo location of computer assets. In the most up to date data we do not have subnets IE 10.81.66.0, we just have the IP address and subnet mask such as 255.255.255.0
...
- 13
4
votes
5
answers
260
views
gcc weird behaviour with bitwise operations
#include <stdint.h>
#include <stdio.h>
int main(){
uint64_t number = 0;
for (uint8_t i = 0; i<4; i++){
number |= 0xFF<<(8*i);
printf("%032lb %lu\n&...
- 41
0
votes
0
answers
67
views
How can one compand (or compress, or pack) four uint8_t values into one uint32_t? [duplicate]
I am sorry, I love C++, and so it is embarrassing that I have to ask: how can I store four uint8_t values in a single uint32_t? Or a uint64_t if necessary. This involves bit-meddling but I lack the ...
- 4,435
1
vote
0
answers
26
views
XOR using Pre-Calculated Weights and Threshold in a Neural Network
I’m trying to implement a threshold-logic (step-activation) network in C++ that computes a 5‑input XOR function. There is no training whatsoever. I already have working code for a 3‑input XOR, but ...
- 11
0
votes
2
answers
151
views
2's complement operator on C
I'm reading The C Programming Language by K & R 2nd edition and got to the bitwise operators. Why, on C, the Complement (~) Operator applied to a N number, returns -(N + 1) ? When it normally just ...
- 11
7
votes
1
answer
365
views
Given an array find all the elements that appear thrice except one element appearing once: how does the optimal approach using bit-manipulation work
I came across LeetCode problem 137. Single Number II:
Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and ...
- 101
2
votes
1
answer
171
views
Optimization and Methods for Reversing Nibbles of a Byte
I'm currently studying encryption and I was coming up with ways of reversing the nibbles of a byte (ex. 0xF5 => 0x5F). I came up with this solution:
byte >> 4 | (byte & 0x0F) << 4
...
- 151
3
votes
2
answers
117
views
Fast algorithm to spread bits of u8 to the LSBs of each byte of a u64
Looking for bit twiddling insights to optimize an algorithm to spread the bits of an 8-bit integer to the LSB of each byte of a 64-bit integer. Example:
0b10110011 -> 0x0100010100000101
The best I'...
- 67
3
votes
3
answers
199
views
How do you obtain the upper 15 bits of a uint16_t?
I have the following 2 bytes to decode: 0000 0000 0111 1011
and I wish to fill this structure
struct ctn
{
uint16_t fx : 1;
uint16_t stn: 15;
ctn() : fx(0), stn(0) {}
} PACKED;
I store ...
- 391
1
vote
2
answers
169
views
Why does this arithmetic right-shift not produce the correct result?
I am working on K&R's exercise 2-8:
Write a function rightrot(x,n) that returns the value of the integer x rotated to the right by n positions.
The implementation I'm using appears to fill in ...
- 55
3
votes
1
answer
124
views
In C language, assuming expression is equal to 0, why !(expression) is also 0?
My gcc version is 12.4.0.
code is below:
int x1 = 0x80000000;
printf("%d\n\n", x1 ^ (~x1 + 1));
printf("%d\n\n", !(x1 ^ (~x1 + 1)));
I though the output should be 0 and 1, since !...
- 31
3
votes
5
answers
178
views
Set bit until a certain index
How do I set the bits of an integer to 1 until a certain index? I can only think of either computing the total value as an unsigned integer or iterating in a loop:
//index in question
int index = 20;
...
user28496108
0
votes
1
answer
75
views
Understanding this bit mask method
I saw an implementation of a bit mask in the following code, but I don't understand how it works. Can someone explain how the expression in the bit mask works? The author's comments are at the top of ...
- 744
1
vote
1
answer
150
views
Efficient seeded random shuffle for the bits in a 32-bit int?
Is there an algorithm that produces an efficient shuffle for a uint32 into a different uint32 that results in a 1:1 mapping when given a changeable random seed?
My initial direction on this is an ...
- 101
1
vote
1
answer
117
views
right shift not working correctly for large longs
when shifting bytes, there are some scenarios that do not seem to make sense, for example
printf("shifted bytes %llx\n",(((long long)1 << 63 ))>>1);
outputs c000000000000000, ...
- 103
0
votes
0
answers
75
views
How do I extract the most significant bits from every byte in a 64-bit integer into an 8-bit bitmask? [duplicate]
Given a 64-bit integer, I'd like to extract all the most significant bits of its eight bytes, and write them to an eight-bit bitmask. That is, I'd like to effectively implement a function auto ...
- 3,503
2
votes
1
answer
133
views
C++ bit compaction
I'm working on a 16 byte array or 128 bits fully populated with the following bit fields:
struct data {
uint ttg : 16; // time to go, units:mins
int volts : 16; // units:10mV
uint ...
- 23
-1
votes
2
answers
140
views
Unexpected output from right rotate function
I was trying to solve the exercise that says
Exercise 2-7. Write the function rightrot(b, n) which rotates the integer b to the right by n bit positions.
and i did code it, here is the code
#include ...
0
votes
0
answers
49
views
DCoder bitwise solution. As I can't see the test cases, it's difficult to understand what I did wrong
I'm using a website called dcoder.tech to help me test how well I use swift. They show you one test case and the results that your code should output. You write a program that takes input, the website ...
2
votes
1
answer
70
views
Very similar functions have noticeably different running times
I have these 2 functions to find the left null space of a matrix over GF(2) for the Quadratic Sieve Factoring Algorithm, given a list of integers(each of which represent a bitarray):
import random
...
- 1,429
-1
votes
1
answer
131
views
Wrong output from custom big unsigned integer type when checking whether subtraction follow modular arithmetic
Here I am tasked with creating an UnsignedBigInteger class that can handle numbers bigger than a long. Am allowed to use a byte array as the internal representation, uint8_t[].
What I came up with is ...
- 1,664
3
votes
1
answer
147
views
Find all x such that (x & (x+y)) == 0
Given an unsigned 64-bit integer y, is there an efficient way to find all unsigned 64-bit integers x such that
(x & (x + y)) == 0?
Some examples for small y:
y=0: only possible solution x=0
y=1: ...
2
votes
1
answer
188
views
Unpredictable value when converting byte array to int | Eclipse Temurin-17.0.10+11
Problem statement:
I am encountering an issue when running the following multi-threaded program. The program spawns a large number of threads (10,000) that process the same byte array value. The issue ...
- 21
3
votes
1
answer
141
views
How to generate an integer that repeats like 100100100…1 in binary with time complexity O(n)?
I am making a function that takes length:int and distance:int as inputs, and output the largest integer that satisfies the following properties in its binary representation:
It starts with 1, ends ...
- 275