For challenges involving doing something on the bit level.
10
votes
9answers
758 views
Super Folding Numbers
We have already defined a folding number here.
But now we are going to define a Super Folding Number. A Super Folding number is a number that if folded enough times it will eventually reach one less ...
35
votes
23answers
2k 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 multiplication ...
41
votes
29answers
3k views
Bitflip and negate
Given an integer, make an expression that produces it from 0 using unary negation - and bitwise complement ~ (~n = -n-1), with the operators applied right to left.
...
-3 = ~-~-~0
-2 = ~-~0
-1 = ~...
13
votes
21answers
2k 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 ...
17
votes
14answers
1k 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 2n items, zero-...
17
votes
12answers
1k views
“Bit-borrow” two numbers
Did you know that a small number can borrow bits from a larger number? Here's an example. Let's say our two numbers 5 and 14. First, write them out in binary:
5 14
000101 001110
First we ...
26
votes
35answers
2k 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 ...
14
votes
9answers
845 views
Compute CRC32 Hash
Credits
This challenge originated from @miles.
Create a function that computes the CRC32 hash of an input string. The input will be an ASCII string of any length. The output will be the CRC32 hash ...
16
votes
23answers
2k views
Generate a parity bit
A parity bit, is one of the simplest forms of a checksum. First, you have to pick the parity, even or odd. Let's say we pick even. Now, we need a message to transmit. Let's say our message is "Foo". ...
19
votes
16answers
2k 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 buffer into chunks of n bits. Right-pad the last chunk with 0s up to n ...
22
votes
10answers
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. ...
4
votes
2answers
215 views
Bit Manipulator/Reader
Introduction
There are often times that we have challenges which require communication of some sort (such as in team KOTH), where density of information may be more important than density of code. ...
11
votes
8answers
429 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 or program that, given an nonnegative integer returns a variable number ...
40
votes
33answers
10k 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:
...
86
votes
15answers
3k 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 N, such that the list consisting of bi = ai XOR N is sorted. If ...
18
votes
17answers
2k 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:
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
This ...
12
votes
6answers
362 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:
a.b.c.d e.f.g.h
where ...
22
votes
21answers
1k 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 ...
15
votes
5answers
289 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 similar to regular primes as you can ...
0
votes
0answers
55 views
Check if a given 8-bit Number is sparse [duplicate]
The task is the following:
Program the shortest fully functional program that checks, if an 8-bit value contains a consecutive sequence of 2 or more ones in its binary form.
If it does contain such ...
35
votes
27answers
5k 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 ...
8
votes
3answers
393 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 ...
26
votes
20answers
3k 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 addition without carrying
101 5
^ ...
15
votes
4answers
812 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 ...
15
votes
5answers
551 views
Unwise bit operations
I like to golf in dc, but I'm sometimes frustrated because dc doesn't have bitwise operations.
Challenge
Provide four named functions which implement the equivalent of the c bitwise operations &,...
26
votes
19answers
3k 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 ...
9
votes
11answers
1k views
Write a program that turns every 17th bit of a text file to a 1
My coworker and I work on a legacy piece of software that we hate sometimes.
Whenever you run it, debug asserts come flying everywhere, and it's never a guarantee that anything will work. The ...
5
votes
8answers
1k views
Extraction of Bits
Your task is to devise a programme that extracts the bits, in order, represented by the first argument based on the set bits represented by the second argument (the mask).
Formal Definition:
Let ...
11
votes
6answers
2k views
Implement an 8 bit adder
The Challenge
Implement a function which accepts two integers whose values range from 0 - 255 and returns the sum of those integers mod 256. You may only use bitwise negation (~), bitwise or (|), bit ...
7
votes
8answers
599 views
Implement bit-wise matrix multiplication
The MMIX architecture is a fairly simple big-endian RISC design. It has a couple of interesting features, one of them is the MXOR instruction, which is what you should implement.
The MXOR instruction ...
4
votes
1answer
263 views
Recover a bzip2 file
The popular .bz2 compression format is used to store all sorts of things. One of the more interesting features is that it consists of several independently decompressible blocks, allowing recovery of ...
22
votes
47answers
5k views
Sort numbers by binary 1's count
Goal
Write a function or program sort an array of integers by the number of 1's present in their binary representation. No secondary sort condition is necessary.
Example sorted list
(using 16-bit ...
6
votes
9answers
1k views
Arbitrarily Shift Bit Array Represented As Array of 32-bit Integers [closed]
Given an array of 32-bit integers which represent a bit array, shift the values by a specified amount in either direction. Positive shifts go to the left and negative values go to the right. This is a ...
