C++

Forum

 
How to deal with MSB?

hunkeelin (159)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
#include <stdio.h>
#define YES ("a palindrome")
#define NO ("NOT a palindrome")
#define CHECK(X) (is_binary_palindrome(X) ? YES : NO)



int is_binary_palindrome(unsigned int n);
unsigned int bin_c (unsigned int a);
unsigned int reverse(unsigned int b);

int main(int argc, char *argv[]) {
  const char testStr[] = "Program thinks %u is %s, should be %s\n";

  printf ("%d",reverse(98374923874923));
  printf (testStr, 0, CHECK(0) , YES);
  printf (testStr, 11, CHECK(11), NO);
  printf (testStr, 9, CHECK(9), YES);
  printf (testStr, 2863289685u, CHECK(2863289685u), YES);
  printf (testStr, 268435456, CHECK(268435456), NO);
  
  getch();
  return 0;
}

/** Returns 1 iff the binary numeral representing N is a palindrome.
 *  Ignores leading 0s. */

unsigned int bin_c (unsigned int a){
  if (a == 0){
	  return 0;
  }
  else{
	  return (a%2 + 10*bin_c(a/2));
  }
}

unsigned int reverse(unsigned int b, int reint){
	static int sum = 0;
	static int base = 1;
	if (reint != 0){
		sum = 0;
		base = 1;
	}

	if (b > 0){
		reverse(b/10,0);
		sum = sum + (b%10)*base;
		base = base * 10;
	}
	return sum;

	
}

int is_binary_palindrome(unsigned int n) {
	
    
	unsigned int binary = bin_c(n);
	unsigned int reverse_binary = reverse(bin_c(n),1);
	if (binary == reverse_binary){
		return 1;
	}
	return 0;	
  
}


My code won't work for printf (testStr, 2863289685u, CHECK(2863289685u), YES);
printf (testStr, 268435456, CHECK(268435456), NO);

that is because the number past MSB.
Last edited on
JewelCpp (87)
1
2
3
4
5
6
7
8
9
10
11
12
 
unsigned int reverse(unsigned int b){
	static int sum = 0;
	static int base = 1;
	if (b > 0){
		reverse(b/10);
		sum = sum + (b%10)*base;
		base = base * 10;
	}
	return sum;

	
}

sum and base are static and you didn't reinitialize them and you used them before in the main
you can corrected by:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
unsigned int reverse(unsigned int b,int reinitialize){
        static int sum = 0;
	static int base = 1;
        if(reinitialize!=0)
        {
             sum=0;
             base=1;
        }
	if (b > 0){
		reverse(b/10,0);
		sum = sum + (b%10)*base;
		base = base * 10;
	}
	return sum;
}

and call it with reverse(n,1);
or make an intermediate function like
1
2
 
unsigned int rev(unsigned int b)
    {return reverse(b,1);}

and use it to call the function outside it
Last edited on
hunkeelin (159)
Thanks! The code is fix but can you explain to me behind the theory behind your fix? I am confuse and I believe if I don't understand it I am going to get into the same trouble later on.
JewelCpp (87)
this function I created is the one the user uses it and not the original one
this function when sending parameter 1 for reinitialize tells the function (because of the fix 
1
2
3
4
5
 
if(reinitialize!=0)
        {
             sum=0;
             base=1;
        }
) that this is the real call of the function and thus reinitialize the variables.
however to save the values so that the function could do the work we do not reinitialise it from inside so we call it with 0 for reinitialize
hunkeelin (159)
Bump edit post and changed question.
JLBorges (13770)
As far as possible, avoid use of local variables with static storage durations.
They impair referential transparency, and are a disaster in the presence of concurrency. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
#include <stdio.h>
#include <stdbool.h>

static unsigned int do_reverse_bits_( unsigned int n, unsigned int reversed_so_far )
{ return n ? do_reverse_bits_( n/2, reversed_so_far*2 + n%2 ) : reversed_so_far ; }

unsigned int reverse_bits( unsigned int n ) { return do_reverse_bits_( n, 0 ) ; }

bool is_binary_palindrome( unsigned int n ) { return n == reverse_bits(n) ; }

void print_bits( unsigned int n ) { if( n > 0 ) { print_bits(n/2) ; printf( "%u", n%2 ) ; } }

int main()
{
    const unsigned int numbers[] = { 64575, 1398101, 911, 262015 } ;

    for( unsigned int i = 0 ; i < sizeof(numbers) / sizeof( numbers[0] ) ; ++i ) // C99
    {
        const unsigned int n = numbers[i] ;
        printf( "%u is %sa binary palindrome. (", n, is_binary_palindrome(n) ? "" : "not " ) ;
        print_bits(n) ;
        puts( ")" ) ;
    }
}

http://coliru.stacked-crooked.com/a/fe0f243577bfd658
hunkeelin (159)
Hi, Thanks. (although I don't have stdbool.h) I would like to know how your code fix the MSB problem? I don't see any memory allocation or some sort. Can you code check whether the binary version of "2863289685" is a pali?
JLBorges (13770)
> I would like to know how your code fix the MSB problem?

The MSB problem does not exist in that code.
No special treatment for the MSB is required for an unsigned integral type.


> Can you code check whether the binary version of "2863289685" is a pali?

http://coliru.stacked-crooked.com/a/bc8dcff4913fb230

Computergeek01 (5613)
(although I don't have stdbool.h)

Here you go:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
/* Copyright (C) 1998-2013 Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.

GCC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

Under Section 7 of GPL version 3, you are granted additional
permissions described in the GCC Runtime Library Exception, version
3.1, as published by the Free Software Foundation.

You should have received a copy of the GNU General Public License and
a copy of the GCC Runtime Library Exception along with this program;
see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
<http://www.gnu.org/licenses/>.  */

/*
 * ISO C Standard:  7.16  Boolean type and values  <stdbool.h>
 */

#ifndef _STDBOOL_H
#define _STDBOOL_H

#ifndef __cplusplus

#define bool	_Bool
#define true	1
#define false	0

#else /* __cplusplus */

/* Supporting <stdbool.h> in C++ is a GCC extension.  */
#define _Bool	bool
#define bool	bool
#define false	false
#define true	true

#endif /* __cplusplus */

/* Signal that all the definitions are present.  */
#define __bool_true_false_are_defined	1

#endif	/* stdbool.h */


Although not having this file means that you really should update your compiler. You can include this one without updating because it doesn't do anything weird. It's just a bunch of macros. Why are you writing in C by the way? I know that project Euler doesn't specify a language, I'm just curious.
Topic archived. No new replies allowed.