spotify-labs-puzzle-3.js

const { performance } = require('perf_hooks')

const cluster = require('cluster')
const os = require('os')

const MAXIMUM_N_VALUE = 1000000000

process.nextTick(main)

function main () {
	if (cluster.isMaster) master()
	if (cluster.isWorker) worker()
}

function master () {
	let thread = 0;

	const samples = [
		{
			input: 13,
			output: 11
		},
		{
			input: 47,
			output: 61
		},
		{
			input: 29,
			output: 23
		}
	]

	for (const {input, output} of samples)
		console.log('sample is ' + (calculate(input) !== output ? 'not valid' : 'valid'))

	const iterations = MAXIMUM_N_VALUE
	const bias = Math.pow(MAXIMUM_N_VALUE, 1 / 3)

	const size = Math.floor(iterations / bias)
	const count = Math.ceil(iterations / size)

	console.log(size, count)

	for (const cpu of os.cpus()) {
		const worker = cluster.fork()
		worker.send({ cpu: cpu, size: size, thread: thread++ })
	}

	cluster.on('exit', (worker, code, signal) => {
		if (worker.error) throw worker.error

		if (thread < count) {
			const replacement = cluster.fork()
			replacement.send({ cpu: worker.cpu, size: worker.size, thread: thread++ })
		}

		if (thread === count) {
			console.log('done?')
		}
	})

	cluster.on('message', (worker, message, handle) => {
		if (message.constructor.name === 'Array')
			return worker.error = message

		const { cpu, size, elapsed, thread } = message

		console.log(`${thread} of ${count}`, elapsed)

		worker.cpu = cpu
		worker.size = size
		worker.elapsed = elapsed
		worker.thread = thread
	})
}

function worker () {
	process.on('message', message => {
		const start = performance.now()
		const { cpu, size, thread } = message

		const cache = new Uint32Array(size)

		for (let input = 0; input < size; input++)
			cache[input] = calculate(input + thread * size)

		for (let input = 0; input < size; input++) {
			const number_input = input + thread * size
			const number_output = cache[input]

			const string_input = number_input.toString(2)
			const string_output = string_input.split('').reverse().join('')

			const string_number = Number.parseInt(string_output, 2)

			if (number_output !== string_number)
				process.send([number_output, number_output, string_number])
		}

		const elapsed = performance.now() - start

		process.send({ cpu, size, elapsed, thread })
		process.exit()
	})
}

function calculate (input) {
	const bits = Math.floor(Math.log2(input)) + 1
	const output = bitReverse(input, bits, bits)

	return output

	function bitReverse (it, maximum, current) {
		const bigPosition = current - 1
		const littlePosition = maximum - current
		const distance = bigPosition - littlePosition

		const big1 = Math.pow(2, bigPosition)
		const little1 = Math.pow(2, littlePosition)

		const bigValue = it & big1
		const littleValue = it & little1

		const bigLittle = bigValue >> distance
		const littleBig = littleValue << distance

		const balance = (maximum / 2 > maximum - current + 1) ? bitReverse(it, maximum, current - 1) : 0

		return bigLittle | littleBig | balance
	}
}

Task

Your task will be to write a program for reversing numbers in binary. For instance, the binary representation of 13 is 1101, and reversing it gives 1011, which corresponds to number 11.