Collect all elements of binary tree that are power of 2

Question

I can't get the following to work. This is what I got so far:

stepen(2).
stepen(X):-
   X mod 2=:=0,
   X1 is X/2,
   stepen(X1).//stepen means power(in Serbian).

spoji([],Y,Y).
spoji([X|Xs],Y,[X|Z]):-spoji(Xs,Y,Z).//spoji means append lists

vadi(nil,[]).
vadi(t(X,L,R),[X|Xs]) :-
   stepen(X),
   vadi(L,SL),
   vadi(R,SR), 
   spoji(SL,SR,Xs).//list of nodes that are power of 2.

Answer 1

You might find this method of determine whether or not N is a a power of 2 a little more efficient. It's a bit-twiddling hack that takes advantage of the two's complement representation of integer values:

is_power_of_two( N ) :-
  integer(N) ,
  N \= 0 ,
  0 is N /\ (N-1)
  .

Edited to note that the property holds true regardless of the sign of the integer: with one exception — 0, hence the test for non-zero — the only two's-complement integer values for which this property is true are powers of two:

?- between(-1025,+1025,N),pow2(N).
N = 1 ;
N = 2 ;
N = 4 ;
N = 8 ;
N = 16 ;
N = 32 ;
N = 64 ;
N = 128 ;
N = 256 ;
N = 512 ;
N = 1024 ;
false.

Answer 2

(So far nobody commented your code. So I will try)

stepen/1 loops

I assume you refer here to the non-negative powers of two. That is, 2^(-1) and the like are not considered.

First of all, your stepen/1 definition produces an error in ISO conforming systems like gnu-prolog or sicstus-prolog.

| ?- stepen(6).
! Type error in argument 2 of (is)/2
! expected an integer, but found 3.0
! goal:  _193 is 3.0 mod 2

This is due to X1 is X/2 which always produces a float or an error, but never an integer. You may replace this by X1 is X div 2 or equivalently X1 is X >> 1.

Will this program now always terminate? After all X div 2 will approach zero. From the negative side, it will end at -1 which then will fail. But from the positive side, it will stay at 0!

Here is the looping program (failure-slice) reduced to its minimum:

?- stepen(0).

stepen(2) :- false.
stepen(X):-
   X mod 2=:=0,
   X1 is X div 2,
   stepen(X1), false. % stepen means power(in Serbian).

As Nicholas Carey has suggested, you can simplify this predicate to:

stepen(X) :-
   X > 0,
   X /\ (X-1) =:= 0.

vadi/2 logic

In your definition, this predicate is true, if all nodes of the trees are powers of two. I assume you wanted to "filter out" the powers. The easiest way to do this is by using DCGs instead of spojii/3 vl. append/3. Let's first consider a simpler case, just the nodes of a tree:

nodes(nil) --> [].
nodes(t(X, L, R)) -->
   [X],
   nodes(L),
   nodes(R).

?- T = t(1,nil,t(2,t(3,nil,t(4,nil,nil)),t(5,nil,nil))), phrase(nodes(T),L).
  T = t(1,nil,t(2,t(3,nil,t(4,nil,nil)),t(5,nil,nil))), L = [1,2,3,4,5].

Now, you no longer want all elements, but only certain, I will use a separate nonterminal for that:

st(E) --> {stepen(E)}, [E].
st(E) --> {\+stepen(E)}.  % nothing!

Or more compactly:

st(E) --> {stepen(E)} -> [E] ; [].

Now, the final non-terminal is:

stepeni(nil) --> [].
stepeni(t(X,L,R)) -->
   st(X),
   stepeni(L),
   stepeni(R).

?- T = t(1,nil,t(2,t(3,nil,t(4,nil,nil)),t(5,nil,nil))), phrase(stepeni(T),L).
T = t(1,nil,t(2,t(3,nil,t(4,nil,nil)),t(5,nil,nil))), L = [1,2,4].

Answer 3

If you consider that 1 is 2^0, you need to change the base case of stepen/1 predicate.

A more important correction is required because your vadi/2 predicate will fail when any node not power of 2 is found in the tree.

Then you should add a clause

vadi(t(X,L,R),Xs) :-
   % \+ stepen(X), this test is not mandatory, but it depends on *where* you add the clause
   vadi(L,SL), vadi(R,SR), spoji(SL,SR,Xs).