[PROG CHALLENGE #024] Non-Corporate Edition

Write a function:

int solution(int N);

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5. Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps.

Stolen from:
https://leetcode.com/problems/binary-gap/

class BinaryGap {

public int solution(int N){

return solution(N, false, 0);
}
public int solution(int N, boolean prevFlag, int memo) {

if(N<2)
return 0;

int remainder = N%2 ;


if(prevFlag){
if(remainder == 0){
memo = 1 + solution(N/2, prevFlag, memo);
} else {
int newGap = solution(N/2, prevFlag, memo);

if(newGap > memo)
memo = newGap;
}
} else {

prevFlag = (remainder == 1);
return solution(N/2, prevFlag, 0);
}

return memo;

}

public static void main(String args[]){
BinaryGap obj = new BinaryGap();

System.out.println(obj.solution(37));
}

}

public int solution(int N) {
int binaryGap = 0;
String binaryString = Integer.toBinaryString(N);
char[] characters = binaryString.toCharArray();
int j = 0;
Character c;
for (int i = 0; i < characters.length; i++) {
c = characters[i];
if (c.equals('0')) {
j += 1;
}

if (c.equals('1')) {
if (j > binaryGap ){
binaryGap = j;
}
j = 0;
}

}
System.out.println(binaryGap);
return binaryGap;

}

class Solution {

public int solution(int N) {
// the longest binary string we need to handle in this problem is 31 bits
final int MAX_STRING_LENGTH = 31;
// the biggest binary gap in our binary string
int maxGapLength = 0;
// variable used for calculation of our binary string
int result = N;
// variable used for storing our binary String
StringBuilder binaryString = new StringBuilder(MAX_STRING_LENGTH);

// O(log N) loop for calculating our binary string
while (result > 0) {
// calculate each bit in the binary string and prepend it to the string (if we add it to the end, we would have to reverse the string after the loop)
binaryString.insert(0, result%2);
result = result / 2;
}

int count = 0;
// loop through our binary string
// O(log N)
for (int i = 0; i < binaryString.length(); i ++) {
// if we encounter a 0, then we increment our count variable
if (binaryString.charAt(i) == '0') {
count++;
}
// if we encounter a 1, then we are finished with our CURRENT gap
if (binaryString.charAt(i) == '1') {
// update our maxGapLength if needed
if (count > maxGapLength) {
maxGapLength = count;
}
// reset count variable so we can count the length of the next gap
count = 0;
}
}

return maxGapLength;
}

}

public static int BinaryGapMaxLengthByIterating(int value, BinaryGapBit bit = BinaryGapBit.Unset)
{
// trackers
int max_gap = 0;
int gap = 0;
char mask = bit == BinaryGapBit.Unset ? '1' : '0';

// convert the value to a binary string
string binary = Convert.ToString(value, 2);

// iterate until the first set bit
int i = 0;
while (i < binary.Length && binary[i] != mask)
{
++i;
}

// we are either at the first set bit or have run out of bits
for (; i < binary.Length; ++i)
{
// check if the current bit is set
if (binary[i] == mask)
{
// check if the current gap is greater than the max candidate
if (gap > max_gap)
{
// promote the current gap count to max candidate
max_gap = gap;
}

// close the running gap count
gap = 0;
}
else
{
// if zero then increase the running gap count
++gap;
}
}

// at this point we have the greatest gap length or zero
return max_gap;
}

public enum BinaryGapBit
{
/// <summary>
/// Look for gaps where the bits are unset.
/// </summary>
Unset = 0,

/// <summary>
/// Look for gaps where the bits are set.
/// </summary>
Set = 1
}

// NEW recursive function
function getGaps (BinaryArray, gaps) {
// finding the first one via its index
const firstOne = BinaryArray.indexOf("1"); if (firstOne > -1) {
// new array created taking a slice of original array
// from the index of the firstOne + 1 index
let NewBinaryArray = BinaryArray.slice(firstOne + 1); // finding second one via its index in new array slice
const secondOne = NewBinaryArray.indexOf("1"); // accounting for no zeros
if (secondOne > 0) {
// adding 2 to our gaps array
gaps.push(secondOne);
}

// Pass array minus second one and gaps array
return getGaps(NewBinaryArray.slice(secondOne +1), gaps);
}

// if gaps array length is empty return 0
// otherwise return largest value in array
return (gaps.length > 0) ? Math.max.apply(Math, gaps) : 0;
}// our function
function solution (N) {

// Tests if our value is an integer
// Tests if N is within range
if (N === parseInt(N, 10) && N >= 1 && N <= 2147483647) {
// Convert to binary
const Binary = N.toString(2).split('');

// calling our recursive function with initial empty gaps
return getGaps(Binary, []);
}

// default if it doesn't meet the requirements
return 0;
}

public static int ComputeLargestBinaryGap(int value)
{
var regexp = new Regex("(?<=1)(0+)(?=1)");
var valueAsBinary = Convert.ToString(value, 2);
return
regexp.Matches(valueAsBinary)
.Cast<Match>()
.Select(m => m.Value)
.DefaultIfEmpty(string.Empty)
.Max(s => s.Length);
}

public int GetBinaryGap(int N)
{
string binaryValue = Convert.ToString(N, 2);

int longestBinaryGap = 0;
int binaryGapLenght = 0;
for (int i = 1; i < binaryValue.Length; i++)
{
if (binaryValue[i] == '1' && binaryValue[i] == '0')
{
binaryGapLenght = 1;
}
else if (binaryValue[i] == '0' && binaryValue[i] == '0')
{
binaryGapLenght++;
}
else if (binaryValue[i] == '0' && binaryValue[i] == '1')
{
longestBinaryGap = Math.Max(longestBinaryGap, binaryGapLenght);
}
}

return longestBinaryGap;
}

int calcGap(char bin[], int bin_size){
int max_gap=0, tmp_gap=0;
bool start = false;

// Iterate through the binary representation of number
for(int i=0; i < bin_size; i++){
// If actual number is '1', then check if previously
// calculated gap is bigger than the one now,
// if it is replace max_gap with new result.
if(bin[i] == '1'){
if(start){
max_gap = max_gap > tmp_gap ? max_gap : tmp_gap;
tmp_gap = 0;
}else{
// This will be executed when first '1' found in string.
start = true;
}
}else if(start){
// Variable start is set to positive number
// when '1' is detected. That means, binary number
// started and from this moment we should count '0's.
++tmp_gap;
}
}

return gap;
}

import unittest

# the largest integer we have to deal with
MAXINT = 2147483647


def solution(N):
"""
Determines the maximal 'binary gap' in an integer
:param N: a positive integer (between 1 and maxint or 2million odd)
:return: a count of the longest sequence of zeros in the binary representation of the integer
"""
# protect against crazy inputs
if not isinstance(N, int):
raise TypeError("Input must be an integer")
if N < 1:
raise ValueError("Input must be a positive integer")
if N > MAXINT:
raise ValueError("Input must be a positive integer less than 2,147,483,647")

# convert the number to a string containing '0' and '1' chars
binary_string = str(bin(N))[2:]

# the longest binary gap: use None to indicate no 'gap' yet found (set to zero at the first flip)
max_count = None
# count the bits in the sequence
this_count = 0
# true if the last bit was a zero
was_zero = None

# loop over all the 0/1 chars in the string
for bit in binary_string:
is_zero = bit == '0'

# if the bit value has flipped
if bool(was_zero) != bool(is_zero):
# the first sequence doesn't count eg: 1111001 has a result of 2
if max_count is None:
max_count = 0
# save the biggest gap
elif this_count > max_count:
max_count = this_count
# reset the counter
this_count = 1
else:
# increment the length of the sequence
this_count += 1

# track what the last bit was
was_zero = is_zero

#print "%s: %s = %s" % (N, binary_string, max_count)
if max_count is not None:
return max_count
else:
# no binary gaps found
return 0



class TestBinaryGap(unittest.TestCase):

def test_example1(self):
self.assertEqual(5, solution(1041))

def test_example2(self):
self.assertEqual(0, solution(15))

def test_extremes(self):
self.assertEqual(0, solution(1))
self.assertEqual(1, solution(5))
self.assertEqual(0, solution(MAXINT))

def test_trailing_zeros(self):
self.assertEqual(solution(6), 0)
self.assertEqual(solution(328), 2)

def test_simple1(self):
self.assertEqual(solution(9), 2)
self.assertEqual(solution(11), 1)

def test_simple2(self):
self.assertEqual(solution(19), 2)
self.assertEqual(solution(42), 1)

def test_simple3(self):
self.assertEqual(solution(1162), 3)
self.assertEqual(solution(5), 1)

def test_medium1(self):
self.assertEqual(solution(51712), 2)
self.assertEqual(solution(20), 1)

def test_medium2(self):
self.assertEqual(solution(561892), 3)
self.assertEqual(solution(9), 2)

def test_medium3(self):
self.assertEqual(solution(66561), 9)

def test_large1(self):
self.assertEqual(solution(6291457), 20)

def test_large2(self):
self.assertEqual(solution(74901729), 4)

def test_large3(self):
self.assertEqual(solution(805306369), 27)

def test_large4(self):
self.assertEqual(solution(1376796946), 5)

def test_large5(self):
self.assertEqual(solution(1073741825), 29)

def test_large6(self):
self.assertEqual(solution(1610612737), 28)

def test_non_int(self):
self.assertRaises(TypeError, solution, 1.0)

def test_zero(self):
self.assertRaises(ValueError, solution, 0)

def test_maxint_plus_one(self):
self.assertRaises(ValueError, solution, 2147483648)


if __name__ == '__main__':
unittest.main()
solution(1)

using System;
using System.Collections;
using System.Data;
using System.Linq;
using System.Text.RegularExpressions;
using System.Windows.Forms;
int IntResult = 0;

public static int BinaryGap1(int val)
{

var rxGap = new Regex("(?<=1)(0+)(?=1)");
var strGap = Convert.ToString(val, 2);

return
rxGap.Matches(strGap)
.Cast<Match>()
.Select(m => m.Length)
.DefaultIfEmpty(0)
.Max();

}


private static int BinaryGap2(int val)
{

BitArray baGap = new BitArray(new[] { val });

int intCount = 0;
int intIndex = -1;

for (int i = 0; i < baGap.Length; i++)
{

if (!baGap[i])

continue;

if (intIndex != -1)
{

int intTemp = i - intIndex - 1;

if (intTemp > intCount)
{

intCount = intTemp;

}

}

intIndex = i;

}

return intCount;

}


public static int BinaryGap3(int val)
{

int intMax = 0;
int intCount = 0;

val |= val - 1;

while (val != val >> 1)
{

val >>= 1;

if ((val & 1) == 1)
{

if (intCount > intMax)

intMax = intCount;

intCount = 0;

}

else

intCount++;

}

return intMax;

}




private void Button1_Click(object sender, EventArgs e)
{

IntResult = BinaryGap1(200890);
MessageBox.Show(IntResult.ToString());

}

private void Button2_Click(object sender, EventArgs e)
{

IntResult = BinaryGap2(200890);
MessageBox.Show(IntResult.ToString());

}

private void Button3_Click(object sender, EventArgs e)
{

IntResult = BinaryGap3(200890);
MessageBox.Show(IntResult.ToString());

}
}

Imports System.Text.RegularExpressions
Private IntResult As Integer = 0
Public Shared Function BinaryGap1(ByVal val As Integer) _
As Integer

Dim rxGap = New Regex("(?<=1)(0+)(?=1)")
Dim strGap = Convert.ToString(val, 2)

Return rxGap.Matches(strGap).Cast(Of Match)().[Select] _
(Function(m) m.Length).DefaultIfEmpty(0).Max()

End Function


Private Shared Function BinaryGap2(ByVal val As Integer) _
As Integer

Dim baGap As BitArray = New BitArray({val})
Dim intCount As Integer = 0
Dim intIndex As Integer = -1

For i As Integer = 0 To baGap.Length - 1

If Not baGap(i) Then Continue For

If intIndex <> -1 Then

Dim intTemp As Integer = i - intIndex - 1

If intTemp > intCount Then

intCount = intTemp

End If

End If

intIndex = i

Next

Return intCount

End Function

Private Sub button1_Click(sender As Object, e As EventArgs) _
Handles button1.Click

IntResult = BinaryGap1(200890)
MessageBox.Show(IntResult.ToString())

End Sub

Private Sub button2_Click(sender As Object, e As EventArgs) _
Handles button2.Click

IntResult = BinaryGap2(200890)
MessageBox.Show(IntResult.ToString())

End Sub

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void intToBin(int n, char* binary, int binary_size){
int pos = binary_size - 1;

while(n > 0){
binary[pos] = n % 2 ? '1' : '0';
n /= 2;
pos -= 1;
}
}

int calcGap(char* bin, int bin_size){
int i, start=0, gap=0, tmp_gap=0;

for(i=0; i<bin_size; i++){
if(bin[i] == '1'){
if(start++){
gap = gap > tmp_gap ? gap : tmp_gap;
tmp_gap = 0;
}
}else if(start){
++tmp_gap;
}
}

return gap;
}

int solution(int N) {
int i, n, bin_size = (sizeof(int) * 8);
char *bin = (char *)malloc(bin_size);
if(bin==NULL){
exit(0);
}
memset(bin, '0', bin_size);

intToBin(N, bin, bin_size);
int gap = calcGap(bin, bin_size);
free(bin);

return gap;
}

def solution(N):
bin_rep = str(bin(N))[2:]
bin_gap = False
bin_max = 0
bin_counter = 0
for symbol in bin_rep:
if symbol == '1':
if bin_max < bin_counter:
bin_max = bin_counter
bin_gap = True
bin_counter = 0
elif bin_gap:
bin_counter += 1
return bin_max

class Solution {
public int solution(int N) {
String binary = Integer.toBinaryString(N);
int i = binary.length()-1;
while(binary.charAt(i)=='0') {
i--;
}
int gap = 0;
int counter = 0;
for(; i>=0; i--) {
if(binary.charAt(i)=='1') {
gap = Math.max(gap, counter);
counter = 0;
} else {
counter++;
}
}
gap = Math.max(gap, counter);
return gap;
}
}

import Foundation

public func solution(N: Int) -> Int {
let binaryString = N.binaryStringRepresentation
var count = 0
var gaps = [Int]()
for char in binaryString.characters {
if char == "1" && count != 0 {
gaps.append(count)
count = 0
} else if char == "0" {
count += 1
}
}
gaps.sortInPlace(>)
guard let first = gaps.first else { return 0 }
return first
}

extension Int {
var binaryStringRepresentation: String {
var binaryDigits: [Int] = []
var quotient = self
var remainder = 0
repeat {
remainder = quotient % 2
quotient = quotient / 2
binaryDigits.append(remainder)
} while quotient != 0
let binaryString = binaryDigits.reverse().map{ String($0) }.joinWithSeparator("")
return binaryString
}
}

1041.binaryStringRepresentation

solution(1041)
@Chess13234

import re
import sys


def get_binary_gap(input_seq):
iterator_zeros = '0'
output = None
if iterator_zeros not in input_seq:
output = 0
else:
while len(iterator_zeros) <= 16:
if iterator_zeros in input_seq:
output = len(iterator_zeros)
iterator_zeros += '0'
return output


def main(arg):
input_seq = arg
if len(input_seq) == 16 and bool(re.match("^[0-1]{1,16}$", input_seq)):
output = get_binary_gap(input_seq)
print(f'The max binary gap of zeros in sequence {input_seq} is {output}')
else:
print(f'invalid input sequence {input_seq}')


if __name__ == '__main__':
arg = str(sys.argv[1])
main(arg)

/**
* 先转换成二进制，再求距离
* @param N
* @return
*/
public static int binaryGap(int N) {

String s = Integer.toBinaryString(N);
int count = 0;
int index = 0;

for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '1') {
index = i;
break;
}
}

for (int i = index + 1; i < s.length(); i++) {
if (s.charAt(i) == '1') {
count = Math.max(count, i - index);
index = i;
}
}

return count;
}

#include <math.h>
#include <stdbool.h>

int solution(int N) {
int highest = 0;
int bin_gap = 0;
int number = N;
bool start_found = false;

for (int c=0; c<(int)log2(number)+1; c++) {
if (N % 2) {
start_found = true;
if (bin_gap > highest)
highest = bin_gap;
bin_gap = 0;
} else {
if (start_found)
bin_gap++;
}
N = N >> 1;
}

return highest;
}

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int solution(int N)
{
int m=1<<30,p=-1,g=0,h=0;
while(!(N&m))m>>=1;
while(m)
{
if((N&m)==p>>1)
g++;
else
{
if(g)
g++;
if(g>h)
h = g;
g = 0;
}
p=N&m;
m>>=1;
}
return h;
}

pub fn longest_gap(n: u32) -> u32 {
let mut l: u32 = 0;
let mut c: u32 = 0;
let mut n_: u32 = n;
while n_ > 0 && n_ % 2 == 0 {
n_ >>= 1;
}
while n_ > 0 {
if n_ % 2 == 1 {
l = std::cmp::max(l, c);
c = 0;
} else {
c += 1;
}
n_ >>= 1;
}
l
}

pub fn longest_gap_cheating(n: u32) -> u32 {
let s = format!("{:b}", n);
let m = s
.split('1')
.rev()
.skip(1)
.map(|x| x.chars().count() as u32)
.max();
match m {
Some(x) => x,
None => 0,
}
}

#[cfg(test)]
mod test {
use super::*;

#[test]
pub fn normal() {
assert_eq!(longest_gap(1041), 5);
assert_eq!(longest_gap(32), 0);
}

#[test]
pub fn cheating() {
assert_eq!(longest_gap_cheating(1041), 5);
assert_eq!(longest_gap_cheating(32), 0);
}

#[test]
pub fn check() {
const NUM_CPUS: u32 = 12;
const ITERS: u32 = 100_000_000;
let p = ITERS / NUM_CPUS;
let mut t = vec![];
for j in 0..NUM_CPUS {
t.push(std::thread::spawn(move || {
for i in j * p..(j + 1) * p {
assert_eq!(longest_gap(i), longest_gap_cheating(i));
}
}));
}
for child in t {
let _ = child.join();
}
}
}

; in: ecx
; out:eax
solution:
xor edx, edx
L1:
shr ecx, 1
jz _ret
jnc L1
xchg eax, ecx
L2:
bsf ecx, eax
cmp ecx, edx
cmova edx, ecx
inc ecx
shr eax, cl
jnz L2
_ret:
xchg eax, edx
ret

24 bytes. It's funny how all the HLL solutions posted above are larger both in source and binary form... so much for HLLs being efficient!

I did this challenge at an interview and was fired because I did not use Code Tags.

>>24
Pull a PR request to owner to include Code tags in every post.
Alternatively develop a 3 line userscript or CSS style to manually set monospaced font and proper spacing/indent.
You could even autoformat each post with minimal overhead importing one of dozen text formatting frameworks as dependency of userscript.

>>25 Solved.
.body{font: monospace; white-space: pre-wrap;}

#include <stdio.h>

char __main__
int main() {
int i;
int a[8];
int b[12];
for (a = 0; a < 12; a++)
printf("You have no idea how hard this is!");
printf("b");
printf("You have no idea how easy this is!");
printf("a[2]");
printf("b[6]");
printf("you're a bad programmer");
printf("")
for (a = 0; a < 2; a++)
printf("\n");

printf("You have no idea how hard this is!");
printf("b");
printf("You have no idea how easy this is!");
printf("a[2]");
printf("b[6]");
printf("you're a bad programmer");
for (a = 0; a < 6; a++)
printf("You have no idea how hard this is!");
printf("b");
printf("You have no idea how easy this is!");
printf("a[2]");
printf("b[6]");
printf("you're a bad programmer");
for (a = 0; a < 6; a++)
printf("You have no idea how hard this is!");
printf("b");

printf("You have no idea how hard this is!");

printf("b");
printf("You have no idea how easy this is!");
printf("a[2]");
printf("b[6]");
printf("you're a bad programmer");
for (a = 0; a < 2; a++)
printf("You have no idea how hard this is!");

printf("You have no idea how hard this is!")

printf("b");
printf("You have no idea how easy this is!");
printf("a[2]");
return -1;
}

http://ai.neocities.org/MsIeAi.html

>>23
this is actually good. probably the only time x86 is useful. it wouldn't be easy to get compilers to output the BSF instruction.

The number of multiple pass solutions is disturbing.

THE STATE of /prague/

Seriously, if you did it any anything longer than O(n) please leave the industry, this isn't your profession.

>>23
Normally I'd argue against using pig dog trojan cpu specific flimjam.

Alas seeing the quality of candidates and you actually having a clue I'll give tripfag a pass.

FIOC3: f=lambda i:max([x.count('0')for x in bin(i)[2:].split('1')])

maybe it can be made shorter in FIOC2 with reduce(), but I don't have time for it now. FIOC3 fucks up reduce() golfing by hiding it in functools module

C: int f(int x){int m=0,c=0;while(x){c=x%2?0:c+1;if(c>m)m=c;x/=2;}return m;}

>>32
Fails on

Given N = 32 the function should return 0, because N has binary representation > '100000' and thus no binary gaps.

i = 0
a = 0
max = 0
while str[i++] == 0 ;
for(c in str)
if c ==

>>28
Because the majority of compiler developers are RISC-worshipping academic imbeciles.

>>35
Even the core of a x86 cpu is RISC, CISC op codes are translated into a lower secret opcoden as they can be pipelined more effectively.

RISC won, get over it.

>>23
Alternative approach with only a single branch in pure C.
Benchmarking is left as exercise to the reader.
http://void.wikidot.com/code:bingap-c

A 32-bit version to directly compare with Cudder asm.bingap32():
12c0: 31 c9 xor %ecx,%ecx
12c2: 31 c0 xor %eax,%eax
12c4: ba ff ff ff ff mov $0xffffffff,%edx
12c9: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)
12d0: 39 c8 cmp %ecx,%eax
12d2: 0f 4c c1 cmovl %ecx,%eax
12d5: 0f bc cf bsf %edi,%ecx
12d8: 0f 44 ca cmove %edx,%ecx
12db: ff c1 inc %ecx
12dd: d3 ef shr %cl,%edi
12df: 0f bc cf bsf %edi,%ecx
12e2: d3 ef shr %cl,%edi
12e4: 85 ff test %edi,%edi
12e6: 75 e8 jne 12d0 <bingap32+0x10>
12e8: c3 retq
12e9: 0f 1f 80 00 00 00 00 nopl 0x0(%rax)



int bingap32(unsigned int N){// a faster pure C bingap using GCC intrinsics
int maxGap=0,gap=0;
do{
maxGap=gap>maxGap?gap:maxGap;//if N has bits set maxGap(initial iteration does nothing)
N>>=__builtin_ffs(N);//strip trailing ones
gap=__builtin_ctz(N);//count trailing zeros
N>>=gap;//strip trailing zeros (Maxgap set at next iteration)
}while(N);
return maxGap;
}

I found bsf has latency of 3, so i rewrote it to use less iterations to squeeze more performance:
v1.15 of bingap:
int bingap32(u32 N){// a faster pure C bingap using GCC intrinsics
int maxGap=0,gap=0;
do{
maxGap=gap>maxGap?gap:maxGap;//if N has bits set maxGap(initial iteration does nothing)
N>>=__builtin_ctz(N);//strip trailing zeros
N>>=__builtin_ctz(~N);//strip trailing ones
gap=__builtin_ctz(N);//count trailing zeros
}while(N);
return maxGap;
}

Assembler:
00000000000012c0 <bingap32>:
bingap32():
12c0: 0f bc cf bsf %edi,%ecx
12c3: 31 d2 xor %edx,%edx
12c5: 31 c0 xor %eax,%eax
12c7: 66 0f 1f 84 00 00 00 nopw 0x0(%rax,%rax,1)
12ce: 00 00
12d0: 39 d0 cmp %edx,%eax
12d2: 0f 4c c2 cmovl %edx,%eax
12d5: d3 ef shr %cl,%edi
12d7: 89 f9 mov %edi,%ecx
12d9: f7 d1 not %ecx
12db: 0f bc c9 bsf %ecx,%ecx
12de: d3 ef shr %cl,%edi
12e0: 0f bc d7 bsf %edi,%edx
12e3: 89 d1 mov %edx,%ecx
12e5: 85 ff test %edi,%edi
12e7: 75 e7 jne 12d0 <bingap32+0x10>
12e9: c3 retq
12ea: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1)

>>21
>>22
>>23
Chad

rest are virgins

>>37
>>38
>>39
Chad too

Managed to squeeze even more cycles by moving cmove to the end.
//delayed compare version
int bingap32_dc(u32 N){// a faster pure C bingap using GCC intrinsics
int maxGap=0,gap=0;//905887818 cycles(see http://void.wikidot.com/code:bingap-c )
do{
N>>=__builtin_ctz(N);//strip trailing zeros
N>>=__builtin_ctz(~N);//strip trailing ones
maxGap=gap>maxGap?gap:maxGap;//if N has bits set maxGap(initial iteration does nothing)
gap=__builtin_ctz(N);//count trailing zeros
}while(N);

return maxGap;
}

>>42
Nice work, only takes 15 seconds to precompute all reasonable values of n up to int_max.

#include <x86intrin.h>

int buffer[2147483647];

int bingap32_dc(int N) {
int maxGap=0,gap=0;
do {
N >>= __builtin_ctz(N);
N >>= __builtin_ctz(~N);
maxGap = gap>maxGap?gap:maxGap;
gap = __builtin_ctz(N);
} while(N);

return maxGap;
}

int solution(int N) {
return buffer[N];
}

int main() {

for (int n=0; n<2147483647; n++)
buffer[n] = bingap32_dc(n);

for (int n=0; n<10; n++)
solution(n);

return 0;
}

This'll turn solution into O(1)

>>36
Only if you believe the marketing...

>>43
Enjoy your RAM latency, lol.

No compiler so far has managed to beat 24 bytes.

>>43
1.Bingap functions operate with unsigned ints.
2.only 5bits are needed to store 32bit binary gap which is 6.4 times less than int(32).
3.calculating int_max binary gaps each time the program starts negates any performance benefits.
4.hardware with less than 8GB will either swap to disk or crash.
5.Uncached RAM access will cause cache flushes as you attempt to read random values from the array.
https://stackoverflow.com/questions/1756825/how-can-i-do-a-cpu-cache-flush-in-x86-windows "The wbinvd instruction takes on the order of 2000-5000 clock cycles to complete!"

>>45

3.calculating int_max binary gaps each time the program starts negates any performance benefits.

Nonsense, it's simply trading space complexity and initial compute time to get O(1) on reads. This approach is pretty common in large scale distributed programming.

4.hardware with less than 8GB will either swap to disk or crash.

It's not 1970 and memory doesn't cost an arm and a leg anymore.

If you still don't believe memory lookup tables can be used for performance please see http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable and/or a modern project like Apache Spark.

>>46
Lookup tables are ok, bit they have to fit in cache(preferably L1) and i have only 7.68GB of ram(*some of 8GB reserved to graphics) and manually disabled all forms of swap.
total used free shared buff/cache available
Mem: 7668728 1923568 3879500 277244 1865660 5648868
Swap: 0 0 0

That Rust solution gave me an itch.

//gcc -std=c99 -Ofast -march=native -mtune=native -pthread
#include <stdio.h>
#include <unistd.h>
#include <pthread.h>

const int MAX_INT = 2147483647;
int buffer[MAX_INT];
int numCPU = 1;

int bingap32_dc(int N) {
int maxGap=0, gap=0;
do {
N >>= __builtin_ctz(N);
N >>= __builtin_ctz(~N);
maxGap = gap>maxGap?gap:maxGap;
gap = __builtin_ctz(N);
} while(N);

return maxGap;
}

int solution(int N) {
return buffer[N];
}

void* worker(void *arg) {

int id = (int)arg;
int chunk = (MAX_INT / numCPU);
int start = chunk * id;
int stop = start + chunk;

for (int i = start; i < stop; ++i) {
buffer[i] = bingap32_dc(i);
}

return NULL;
}

int main() {

numCPU = sysconf(_SC_NPROCESSORS_ONLN);
pthread_t threads[numCPU];

for (int i = 0; i < numCPU; ++i)
pthread_create(&threads[i], NULL, *worker, (void *)i);

for (int i = 0; i < numCPU; ++i)
pthread_join(threads[i], NULL);

return 0;
}

It's not 1970 and memory doesn't cost an arm and a leg anymore.

Fucking idiot.

>>49

Apologies for my outburst.

>>49
He's not wrong

>>23,44
Why doesn't this work on my ODROID-XU4?

function runcount(int x){
i=0; j=0; k=0;
j=x & 0x01;
while(x >=1){
x = x>>1;
i++;
((x & 0x01) == j) || i=0;
if (i>k) k = i;
j = x & 0x01;
}
return k;
}

function gapcount(int x){
i=0; k=0; //j=0;

while(((x & 0x01) ==0) && (x>=1))
x = x>>1;

while(x >=1){
x = x>>1;
i++;
((x & 0x01) == 0) || i=0;
if (i>k) k = i;
}
return k;
}

Devil dubs