Questions tagged [bitwise]
Bitwise refers to a bitwise operation which operates on one or more bit patterns or binary numerals at the level of their individual bits.
335 questions
7
votes
2
answers
246
views
Bit manipulation to find a monochromatic clique on k vertices knowing all on k-1 vertices
I have a very hot segment of code in a large project. I've extracted the relevant segment and a toy example to illustrate it.
The project involves an unavoidable combinatorial explosion related to ...
- 173
13
votes
8
answers
2k
views
Counting Occurrences of a Specific 3-Bit Pattern in a Byte Array
I was asked this problem in an interview, and this is the solution I came up with. I was told it's not the most efficient solution, but I can't think of any other solution. This is the problem.
...
- 133
6
votes
2
answers
94
views
TypeScript Number Set
I originally premiered this code to the internet in this StackOverflow post, and per a recommendation through one of the comments, I am reposting it here.
I am making a floating-point number set ...
- 161
2
votes
0
answers
57
views
A machine learning model for predicting bit strings in Java
I have this GitHub repository (BitPredictor.java). Basically, I tried to harness a machine learning model for predicting bit strings. I have implemented it to the best of my understanding and have ...
- 29.8k
5
votes
1
answer
238
views
String character changes (case insensitive) - Go
I saw this question on one of the socials, presented as an Apple interview question. I have had to paraphrase as it was not given in text format. (Credit: Instagram @greghogg5)
Given a string (S) ...
- 53
2
votes
0
answers
86
views
Implementing Generic, General, Specific and Portable Bitwise Operations
First my apologies. My mental faculties currently leave rather a lot to be desired and I have thus spend an inordinate amount of time on this pet project of mine, testing myself if you will.
I find it ...
- 373
1
vote
1
answer
107
views
Bit vector in Java supporting O(1) rank() and O(log n) select() - follow-up
(This post is the continuation of Bit vector in Java supporting O(1) rank() and O(log n) select(). It resides here (version 1.0.1).)
Basically, I have implemented everything harold suggested, except ...
- 29.8k
1
vote
1
answer
164
views
Bit vector in Java supporting O(1) rank() and O(log n) select()
Introduction
I have this GitHub repository (version 1.0.0.). It implements a rank(i) operation in \$\Theta(1)\$ time, and ...
- 29.8k
3
votes
2
answers
115
views
Unpacking a byte into 8 bytes, where the LSB of each byte corresponds to a bit of the original byte
I needed to unpack a byte into the LSBs of each byte in an 8-byte integer. After some testing, I derived a surprisingly efficient and elegant solution that uses magic numbers multiplication, though ...
- 948
5
votes
1
answer
284
views
Space efficient arrays
I needed a very space-efficient structure to store an array for which elements are unsigned integers with an upper bound known at runtime.
I'm not an expert in pointer arithmetic, so I'm not sure if ...
- 151
5
votes
2
answers
2k
views
C Bit Utility Functions: Popcount, Trailing Zeros Count, Reverse All Bits
Here are some utility bitwise functions for 64 bit integers. I have independently derived inv64 (inverse all bits) and pcnt64 (...
- 948
7
votes
2
answers
1k
views
Convert 64-bit Gray code to integer
This algorithm encodes a 64 bit integer.
As input I have a 64 bit integer a, for example:
(a is a single 64 bit number,which I split in 8 bytes for readability) <...
- 173
2
votes
1
answer
75
views
Finding the kth smallest number where all (hexadecimal) digits are different
I'm mostly trying to understand why the simpler char array mask below (to track which digits have been already used) is much ...
1
vote
0
answers
161
views
Interleave Bits Generically
This commonly referenced "bit twiddling" site has an interesting algorithm for interleaving the bits of two 32-bit integers. Here is my attempt at completely generalizing the algorithm using ...
- 1,940
6
votes
3
answers
816
views
C++ Bitwise adjacency matrix implementation
I have tried to implement a bitwise adjacency matrix to represent a graph with a fixed number of vertices.
Instead of wastefully representing each connection with an integer, 64 connections are ...
- 163
2
votes
1
answer
114
views
Leetcode 137: Single Number II -- python bit operations
I solved LeetCode 137 in C++. TLDR of the problem: array of numbers, nums is given; all numbers appear 3 times, except one which appear only once. Find the number ...
- 322
3
votes
1
answer
85
views
Access integer field in network packet
I see three complexities in accessing (reading/writing) integer field in network packet.
Handle endianness. Integer in network packet is big-endian (BE). The host may be either big-endian or little-...
- 828
3
votes
3
answers
1k
views
Compute the sum of even numbers between two values
Recently I was watching two YouTube videos criticizing a function which sums the even elements in an inclusive range, the original function looks like this:
...
- 145
4
votes
2
answers
165
views
Less redundant and clearer implementation of action triggers from two modules
(Before I even start: For reasons beyond my control, this code base is constrained to C++98 (so, no =delete, no auto etc., but ...
3
votes
1
answer
464
views
Portable integer to/from little endian conversion in C
Integers need to be converted to a byte array of defined endianness to be reliably and consistently saved and transmitted, and converted back to be accurately received and read. The goal is to be as ...
- 948
1
vote
1
answer
60
views
SortedIntSet: a set of integers that can be iterated in ascending order in O(N) time
I needed a set with the following properties:
can be iterated in ascending or descending order in \$O(N)\$ time
the usual set operations (contains, add, remove, discard) can still be done in \$O(1)\$
...
- 486
0
votes
1
answer
315
views
Integer multiplication without using multiply operator
I wrote a method that multiplies two integers. Is there a faster approach that doesn't use the * operator?
The method mult(a, b) ...
- 111
2
votes
1
answer
561
views
Electronic circuit logic gates simulator
I've seen a lot of C++ simulators implementing logic gates, but absolutely all of them use the wrapped bitwise operations of the programming language itself. I have tried to omit the use of a bitwise ...
- 155
1
vote
4
answers
180
views
Counting initial bits of 0 in Java
I want to count the number of bits set to 0 at the beginning of a byte array. So far the code I have is this:
...
- 19
3
votes
1
answer
1k
views
Convert a c# decimal to big-endian byte array
Following the avro schema documentation for decimals I've created a method to turn a decimal into a byte array. The goals are:
Should be represented by a non-scaled integer
Should be big-endian
I've ...
- 155
1
vote
1
answer
321
views
C++ Chess Engine - (Magic)Bitboard-based move generation
I am currently writing a bitboard-based Chess Engine in C++, and I recently finished the move generation. I am using move-lookup-tables that get pre-calculated at application startup for sliding and ...
- 350
4
votes
2
answers
1k
views
4
votes
1
answer
485
views
Calculate Hamming distance between integers with bitwise operations
I recently learned about the Hamming distance. The use-case I found it through was actually working with integers instead of strings, yet its implementation was using string comparison. I was pretty ...
- 929
1
vote
4
answers
182
views
Permuting BitSet in Java
I have this tool for permuting bits in BitSets:
com.stackexchange.codereview.util.BitPermutation.java:
...
- 29.8k
3
votes
1
answer
560
views
(Google Foobar XOR Checksum Challenge) How do i optimize this function to run for much larger values?
I wrote a function that accepts 2 integers start and length as input and returns the bitwise XOR of certain numbers as described below:
...
- 39
0
votes
3
answers
876
views
0
votes
2
answers
1k
views
Separating odd numbers and even numbers into two vectors in C++
I'm learning C++, and would like some guidance. I'm pretty sure I'm doing something wrong.
This algorithm runs in O(n) time and uses O(n) external space. Could I make a more efficient algorithm for ...
- 13
4
votes
1
answer
96
views
LetterDict, a dictionary whose keys must be lowercase letters [a-z]
Looking for any suggestions - alternative design, improvements to readability, improvements to the comments, etc.
I implemented this letter dictionary to see if it would faster than a regular ...
- 486
0
votes
1
answer
96
views
Recursive function that gives the number of hashes present in a Merkle Mountain Range proof
I have written a function that gives the number of hashes present in a Merkle Mountain Range proof. Using Solidity, this function can be written as:
...
- 175
0
votes
1
answer
163
views
Transformations on a game board represented as a bitset
I'm using a long as a bitset to represent a game board. If a field is set (X) the corresponding bit is set, if it's empty (...
- 131
4
votes
0
answers
112
views
Barebones DNS Client in Rust
I'm starting to learn about networking and as a project I am building a really simple DNS client in Rust.
Functionality to start was just to take a command line domain argument and sending a DNS A ...
- 141
8
votes
2
answers
1k
views
Representing Tic-Tac-Toe using a binary BitBoard
So I have been learning more about binary numbers lately, particularly
in related to describing a gamestate. While perhaps chess is the most natural candidate I wanted to start of with something ...
- 5,725
3
votes
4
answers
106
views
Move an unaligned bit-addressed range into another bitmap
Context
I have an array of maximum-fixed-size, size, containers of items; these items are either pointers to objects or an index of the same array, (but no loops.) ...
- 1,080
2
votes
2
answers
125
views
Generate mask for non zero (or inverse) nibbles in integer
Apologies for the cryptic title, but the problem really is rather simple.
I have a 64 bit integer which I interpret as 16 4 bit nibbles, or a nibble array if you wish, and I needed generate a mask ...
- 373
2
votes
3
answers
83
views
How to refactor a method with many prameters that sets a bit array
I've written a method that is going to set a bit array by passing bool parameters to be able send correct command
...
- 21
1
vote
0
answers
134
views
Generating Unique Subsets using Bitmasking
Given an array arr[] of integers of size N that might contain duplicates, the task is to find all possible unique subsets.
Link to the judge: LINK
Note: Each subset should be sorted.
Example 1:
...
3
votes
1
answer
301
views
Invert n bits beginning at position p of an unsigned integer
In an attempt to create a function that returns x with the n bits that begin at position p ...
1
vote
2
answers
261
views
Determine whether bitwise-OR of sub-array is odd
Problem:
Given an array A of N integers, you will be asked Q queries. Each query consists of two integers L and R. For each query, find whether bitwise OR of all the array elements between indices L ...
4
votes
0
answers
642
views
BitVector64 implementation
I have implemented a structure to handle BitVector64 (default System library support only 32 bits).
In the implementation i have added some custom method to manipulate bits inside the vector.
I would ...
- 248
4
votes
1
answer
2k
views
Generically convert bytes to integers
I wanted to know If there was a way to make it more versatile or shorter/simpler. Here's the code:
...
3
votes
2
answers
1k
views
Random alphanumeric string generator function (C, Windows, bcrypt.h)
The function uses the Windows "Cryptography API: Next Generation" (bcrypt.h)'s BCryptGenRandom function to generate ...
- 31
5
votes
1
answer
84
views
Bitarr class optimization C++
I have implemented a bitarr class that does bit manipulations. I would love to know if there is any way to make the code more optimized. Any input would be much appreciated. Thank you! Note: int main()...
- 369
4
votes
2
answers
606
views
5
votes
2
answers
663
views
How to optimize bitwise get/set/clear of ranges of bits on 8-bit integers in JavaScript?
I have been working for a few days on writing get, set, and clear bitwise functions in ...
- 321
3
votes
1
answer
66
views
Array-like data structure for fixed sized types with non-machine-word sizes
I am writing an array-like data structure for types other than 8 16 32 64 – the usual type sizes.
Ideally, my interface is the following for addressing the array.
...
- 51