Skip to main content

Questions tagged [bitwise]

For challenges involving bitwise commands or manipulation of numbers at the bit level

Filter by
Sorted by
Tagged with
18 votes
12 answers
2k views

Is it a valid ARM immediate value?

Exposition In this challenge, I am talking about ARM assembly language. ARM is a 32-bit RISC processor; I'll use instruction set up to architecture v6. To load a constant ("immediate") value ...
44 votes
39 answers
6k views

Programming with Bits and Bytes

In this challenge you are going to write an interpreter for a simple language I've made up. The language is based on a single accumulator A, which is exactly one byte in length. At the start of a ...
16 votes
6 answers
877 views

Golf this Thumb-2 Constant!

One thing that is constantly frustrating when golfing ARM Thumb-2 code is generating constants. Since Thumb only has 16-bit and 32-bit instructions, it is impossible to encode every immediate 32-bit ...
13 votes
23 answers
2k views

Alternating bit smearing

Introduction This challenge requires you to set the trailing zeros of an integers binary representation to 010101…, this is best explained with an example: Given ...
17 votes
18 answers
2k views

XOR of independent Bernoulli variables

In probability theory, a Bernoulli variable is a random variable which has a single parameter \$p\$, and is equal to 1 with probability \$p\$, and 0 with probability \$1-p\$. In this challenge, there ...
47 votes
35 answers
15k views

XOR multiplication

You goal is to implement the operation of XOR (carryless) multiplication, defined below, in as few bytes as possible. If we think of bitwise XOR (^) as binary ...
34 votes
36 answers
6k views

Calculate the longest series of 1's in an integer's binary value

Goal Given a non-negative integer, create a function that returns the starting position of number of largest consecutive 1's in that integer's binary value. When given an input ...
31 votes
44 answers
3k views

Mean bits: an average challenge

Given an integer N >= 1, output the mean number of bits in an integer from 0 to N - 1 Specification The output can be calculated as the sum of the number of bits in the binary representation of each ...
1 vote
0 answers
158 views

making a binary string palindrome using xor operations [closed]

Problem You are given a binary string A of length N. You can perform the following type of operation on the string A: Choose two different indices \$i\$ and \$j\$ (\$1 \le i\$, \$j \le N\$) Change \$...
39 votes
77 answers
22k views

Sort numbers by binary 1's count

Goal Write a function or program sort an array of integers in descending order by the number of 1's present in their binary representation. No secondary sort condition is necessary. Example sorted ...
15 votes
3 answers
563 views

Count the number of disjoint 11 blocks

The task is to count the number of disjoint 11 blocks in a 64-bit word, using the minimum number of straight-line instructions. That is, how many nonoverlapping ...
26 votes
17 answers
3k views

Toggle some bits and get a square

Given an integer \$N>3\$, you have to find the minimum number of bits that need to be inverted in \$N\$ to turn it into a square number. You are only allowed to invert bits below the most ...
8 votes
2 answers
606 views

Inverting string-based binary number in one line in Python

I want to read two strings on separate lines, each string the same length and containing only 0's and 1's, and determine if the first is the one's complement of the second. How succinctly can this be ...
2 votes
3 answers
308 views

Shift distance of number [closed]

Given two non-zero 16-bit integers a and b, decide the smallest number of shift operations needed to turn ...
8 votes
3 answers
373 views

Smallest and largest 100-bit square with maximum Hamming weight

Introduction In the binary representation of a \$k-\$bit \$(k>1)\$ square number \$n^2, \$ not all bits can be \$1\$. The maximum number of \$1\$-bits (Hamming weight, \$B\$ for short) is given in ...
19 votes
32 answers
8k views

Find the number of leading zeroes in a 64-bit integer

Problem: Find the number of leading zeroes in a 64-bit signed integer Rules: The input cannot be treated as string; it can be anything where math and bitwise operations drive the algorithm The ...
19 votes
22 answers
5k views

Decode a variable-length quantity

A variable-length quantity (also referred to as VLQ or uintvar) is a way to encode up to a 28 bit integer value using only as many bytes as necessary. This was used ...
23 votes
36 answers
13k views

Reverse Bit Order of 32-bit Integers

Write the shortest code to reverse the bit order of a 32-bit integer. Rules: Input is assumed to be a valid integer or string equivalent if your language doesn't support numerical values (e.g. ...
23 votes
30 answers
3k views

Produce an XOR table

Introduction XOR is a digital logic gate that implements an exclusive or. Most of the times, this is shown as ^. The four possible outcomes in binary: ...
10 votes
32 answers
2k views

Do two numbers contain unique powers of 2

Break two numbers up into their powers of 2, if they share any, return a falsey value. Otherwise, return a truthy value. If one input is 0, the answer will always ...
41 votes
34 answers
13k views

Cheating a multiple choice test

Introduction While studying, I tried to come up with several ways to cheat a multiple choice test. It basically is a compressed version of the multiple choice answers. The method goes as following: ...
11 votes
8 answers
643 views

Bijective mapping from integers to a variable number of bits

A variable number of bits is an array of 0 or more bits. So [0, 1] is a variable number of bits, but so is []. Write a function ...
22 votes
22 answers
8k views

Floating Point XOR

Your task is pretty simple. Given two floats, bitwise xor the binary representation of them, and output that as a float. For example, ...
29 votes
30 answers
4k views

Bit-Reversal Permutations

Your goal is to create a function or a program to reverse the bits in a range of integers given an integer \$n\$. In other words, you want to find the bit-reversal permutation of a range of \$2^n\$ ...
4 votes
19 answers
573 views

Double bit rotation to the right [closed]

Given a positive integer as input, output that integer, but with its bits rotated two times to the right. Also, think of the number as a donut of bits, eg. ...
0 votes
4 answers
129 views

Calculate the truncated log2 of some unsigned integer [duplicate]

Definition Given some number, x calculate the smallest number i such that 2i≥x. This is not a duplicate of this question. It is slightly different in that an input of 16 should yield an output of 4 ...
23 votes
25 answers
2k views

Compute the Binary Sierpinski Triangle Sequence

The Binary Sierpinski Triangle sequence is the sequence of numbers whose binary representations give the rows of the Binary Sierpinski Triangle, which is given by starting with a 1 in an infinite row ...
14 votes
22 answers
3k views

Golf bit weaving

Note: the first half of this challenge comes from Martin Ender's previous challenge, Visualize Bit Weaving. The esoteric programming language evil has an interesting operation on byte values which it ...
22 votes
11 answers
2k views

The XOROR sequence

Cellular Automata are truly fascinating. The ones that are usually talked about are the binary ones, i.e., the ones representable by a number. However, those, in my opinion, have been done to death. ...
12 votes
30 answers
1k views

String to Bit Transition

Task Given an input string of one or more ASCII characters which codepoints are between 0 and 128 (exclusive), do the following: Convert each character into its 7-bit ASCII code (if the ASCII code is ...
6 votes
3 answers
387 views

Dr. Lamport's Unfinished Business

Introduction Dr. Leslie Lamport, of the eponymous Lamport one-time signature scheme, is getting rather old. But he can't die until his most famous algorithm gets all the kinks ironed out! In ...
21 votes
7 answers
2k views

Find the XOR Primes

In this challenge posed by xnor, we were asked to implement XOR multiplication. In this challenge the goal is to find the first n XOR primes. XOR primes are very ...
18 votes
4 answers
956 views

Shifty XORyption

Write a program or function (or set of programs/functions) to encrypt and decrypt data given the following specification: Encryption Calculate an XOR hash of the input by XOR-ing every byte with ...
110 votes
18 answers
6k views

Xorting an array

Conceptually, this challenge is really simple. You're given a list of non-negative integers ai. If possible, find a non-negative integer ...
18 votes
9 answers
1k views

The Koszul Sign Rule

A Bit of Background The exterior algebra is a central object in topology and physics (for the physics concept cf. fermion). The basic rule dictating the behavior of the exterior algebra is that \$yx =...
12 votes
9 answers
1k views

Simulate D Flip-Flop

Objective Simulate an edge-triggered D Flip-Flop. What is D Flip-Flop? A D flip-flop is an electronic digital device that outputs an inputted data (abbr. D) with synchronization to a clock (abbr. ...
16 votes
23 answers
2k views

Summing a sub-square of a quarter of an infinite chessboard

Description of the problem Imagine a quarter of an infinite chessboard, as in a square grid, extending up and right, so that you can see the lower left corner. Place a 0 in there. Now for every other ...
28 votes
12 answers
4k views

Compress 8 bits to 6 when certain bit patterns will never occur

Consider an eight bit number in which an even position bit will never be 1 if one of its neighbors is 0 (considering MSB and LSB as neighbors). There are fewer than 64 such numbers, so there is at ...
7 votes
13 answers
214 views

Computational Parity Party! [duplicate]

The computational parity of an integer is defined as 1 if the integer has an odd number of set bits, and 0 otherwise. (src). Input You will receive one nonnegative integer that you will take the ...
-2 votes
7 answers
426 views

Interpreting the Wolfram Code

Introduction An elementary cellular automaton is a cellular automaton that is 1-dimensional and has 2 states, 1 and 0. These cellular automata are categorized based on a simple code: the Wolfram code,...
15 votes
8 answers
1k views

Summation under Zeckendorf Representation

Zeckendorf's theorem shows that every positive integer can be uniquely represented as a sum of non-adjacent Fibonacci numbers. In this challenge, you have to compute the sum of two numbers in ...
24 votes
27 answers
7k views

Split a byte array into a bit array

Write a function that when given a buffer b (1 - 104857600 bytes long) and a number of bits n (1 <= n <= 64), splits the ...
16 votes
5 answers
2k views

Binary Convolution

A binary convolution is described by a number M, and is applied to a number N. For each bit in the binary representation of <...
-2 votes
2 answers
287 views

Mirror, Mirror, on the wall. Who's the fairest of them all?

Well, you know it's Snow White, and the evil Queen is at it again. Will Snow White be saved? Will she fall asleep once again? Will the Prince find her? Challenge: Given an arbitrary number (>= 2) ...
29 votes
20 answers
4k views

Vampire Compatibility

A little known fact about vampires is that they must drink the blood of victim that has a compatible donor blood type. The compatibility matrix for vampires is the same as the regular red blood cell ...
37 votes
27 answers
3k views

Folding Numbers

Given a number determine if it is a folding number. A folding number is a number such that if you take it binary representation and "fold" it in half, That is take the result of XNOR ...
22 votes
19 answers
2k views

Different number, same weight

Background The Hamming weight of an integer is the number of ones in its binary representation. For this challenge, integers are represented with 32 bits, and they are unsigned. Challenge Given an ...
31 votes
2 answers
1k views

Can a neural network recognize primes?

Background Recognizing primality seems like a poor fit for (artificial) neural networks. However, the universal approximation theorem states that neural networks can approximate any continuous ...
11 votes
7 answers
555 views

Mask an IP address and give its broadcast

Background Inspired by this Unix.SE question (and of course my own answer). When an IP address is specified for an interface, it is often given in this dotted-decimal form: ...
1 vote
1 answer
259 views

(bit)Wise Images [closed]

Given a truth table and two images, use the truth table as a bitwise operation to the two images. For example with the truth table: 1 0 1 0 0 0 1 0 (Note that ...